Try to search your question here, if you can't find : Ask Any Question Now ?

No of pairs of strings which when joined contain all vowels

HomeCategory: stackoverflowNo of pairs of strings which when joined contain all vowels
julie asked 3 weeks ago

I am facing difficulty with a question:

I have N words with me. For each valid i, word i is described by a
string Di containing only lowercase vowels, i.e. characters ‘a’, ‘e’,
‘i’, ‘o’, ‘u’.

What is the total number of (unordered) pairs of words such that when
concatenated, they contain all the vowels?

I have written some code in C++, that works as follows: I have created a bit array that sets positions of the vowels and then I checked all pairs of strings whether they contain all vowels by comparing with the string ‘complete’ which has all bits set corresponding to the vowels.

#include<bits/stdc++.h>
using namespace std;

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;

    int con_s[n];
    for(int i=0;i<n;i++)
    {
      string s;
      cin>>s;
      con_s[i]=0;
      for(int j=0;j<s.length();j++)
      {
        con_s[i] = con_s[i] | (1<<(s[j]-'a'));
      }
    }
    int complete = 0;
    complete = (1<<('a'-'a')) | (1<<('e'-'a')) | (1<<('i'-'a')) | (1<<('o'-'a')) | (1<<('u'-'a'));
    // cout<<complete;
    int count = 0;
    for(int i=0;i<n-1;i++)
    {
      for(int j=i+1;j<n;j++)
      {
        if((con_s[i] | con_s[j])==complete)count++;
      }
    }
    cout<<count<<"n";
  }
  return 0;
}

But my code is not optimised enough. Can anyone suggest an efficient solution ?

Test Case:

3
aaooaoaooa
uiieieiieieuuu
aeioooeeiiaiei

O/P:

2

Explanation:
Pairs (1 and 2) and (2 and 3) on concatenation contain all 5 vowels while pair (1 and 3) does not contain ‘u’. Hence O/P is 2.

Constraints:

1≤T≤1,000
1≤N≤105
1≤|Di|≤1,000 for each valid i
the sum of all |D_i| over all test cases does not exceed 3⋅107
1 Answers
Best Answer
Amit answered 3 weeks ago
Your Answer

1 + 9 =

Popular Tags

WP Facebook Auto Publish Powered By : XYZScripts.com