Problem

I have $N$ words. For each valid $i$, word $i$ is described by a string $D_i$ containing only lowercase vowels, i.e. characters 'a', 'e', 'i', 'o', 'u'.

We check the number of strings $D_i$ and $D_j$ which, when concatenated into a new string $M$, contain all 5 vowels. What is the total number of (unordered) pairs of words such that when concatenated, they contain all the vowels?

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.


• The first line of each test case contains a single integer $N$.


• 
  $N$ lines follow. For each valid $i$, the $i^{th}$ of these lines contains a single string $D_i$.

Output

For each test case, print a single line containing one integer - the number of concatenated words that contain all vowels.

Test Case

3

aaooaoaooa

uiieieiieieuuu

aeioooeeiiaiei

Output

2

Constraints

• $1≤T≤1,000$


• $1≤N≤10^5$


• 
  $1≤|D_i|≤1,000$ for each valid $i$
  


• the sum of all |$D_i$| over all test cases does not exceed $3⋅10^7$
  

I have written some code but I want to optimize it:

#include<bits/stdc++.h>

using namespace std;



int main()

{

  int t;

  cin>>t;

  while(t--)

  {

    int n;

    cin>>n;

    vector<string> v;

    long long  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'));

      }

    }

    long long 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;

}

Can you please suggest a more optimized solution...

I'm no C++ guru, but some things jump out at me:

1. 
   

   Your coding style is very dense, which makes it hard to read and review. I'd suggest that you switch to a style that doesn't make you pay for each time you add a space. Code like this:

   
   
   

   cin>>t;
   
   while(t--)
   
   

   
   
   

   Just isn't as easy to read as code like this:

   
   
   

   cin >> t;
   
   while (t--)
   
   

   
   
   

   The little things make a difference! And even if you're in some kind of "shortest code" context, I think you should still write it long, and then compress it once you have it working.

   
   



2. The first for loop in your while loop is concerned with reading and parsing the input strings. I believe you should break that into a separate function. What's more, I think you should make a slight change to your data storage as @Deduplicator suggested: instead of just using the bits located at (1 << (vowel - 'a')), at some point you should compress the bits down into the range 1<<0 .. 1<<4.




3. I believe that the description says "(unordered) pairs" and means that if two strings, A and B, can be concatenated to meet the requirements, they only count once, as in set{A, B} and not twice, as in pair(A,B), pair(B,A). So, as @Deduplicator suggested, if you "bin" your words - that is, categorize them according to the trait "which vowels are present", then you can represent a bin with just an integer (how many words are in the bin). So you would then cross-match every bin with every other bin to determine whether the binned words can successfully pair, and add an appropriate number to the count.

With that in mind, a successful solution would look something like this:

for each input word:

    scan the word for vowels, recording which vowels were found

    classify the found vowels into a small integer with bits 0..4 set

    use the small integer as the "bin" number for that word

    increment the count for that bin#

This should be $O(n cdot s)$ on the number of words, n, and the length of the words, s, in time. The only optimization would be to break out of the scanning loop if you match every single vowel, since further scanning gains you nothing. The code will require storage for the input, but compiles everything down to a single bin number, so the storage will be from $O(1)$ to $O(s)$ depending on how you implement the code. The bin numbers are members of a fixed set, so their counts will be $O(2^5)$ regardless, which simplifies to $O(1)$.

Now since matched pairs of words only count one time, you can loop "upwards" when generating combinations:

for each bin 0 .. 2^5 - 1

    for each higher bin (looping upwards here):

        if the two bins match

            the count of word pairs is # in bin-1 * # in bin-2

            add the count to the total count of matchable pairs

This should be $O(n^2)$ on the number of bins (not words!), which is a constant. You can't optimize much, except that bins with counts of zero won't contribute anything so can be skipped.

At this point you have your answer and just need to print it out.

Your Code:

1. Don't use <bits/stdc++.h>, it's unportable and inefficient. See "Why should I not #include <bits/stdc++.h>?" for the details.




2. Don't use using namespace std;, that namespace just isn't designed for it. See "Why is “using namespace std” considered bad practice?" for more background.




3. Invest in some better names. Being too parsimonious there hurts, even though brevity is a virtue.



4. 
   

   Format your code consistentently.

   
   
   
   
   
   • Sometimes you have space around binary operators (other than comma), sometimes you don't.
   
   
   • Also add a space after #include, for, if, and while.
   
   
   • You don't have to use a block for single statements, but please don't put them on the same line, at the least separate them with a space.
   
   
   
   



5. C++ does not have VLAs. Just use a std::vector instead.




6. While in general, keeping the scope of a variable minimal is a good idea, there are exceptions. One of them is efficiency. Always spinning up a new std::string means being unable to re-use the buffer. Not that you really need the whole string at once, anyway.




7. One reason you should minimise a variables scope, is that it allows you to initialise it to the proper value, instead of leaving it uninitialised or, horrors of horrors, adding a spurious dummy-initialisation.
   
   That also allows you to avoid writing the type (Almost Always auto), and making it const or even constexpr.




8. There are compound-assignment-operators for most binary operators. Like a |= b for a = a | b. Using them leads to shorter, more readable code.




9. When you want to output a single character, why not use a character-literal? It's potentially even slightly more efficient.




10. return 0; is implicit for main(). Take it or leave it, but be aware.

The Algorithm:

Your algorithm uses $O(#characters+#words^2)$ time and $O(max_word_length + #words)$ space.

An optimal algorithm only needs $O(#characters+2^{#vowels})$ time and $O(1)$ space:

1. For every word:
   
   
   
   
   1. Set the bits for all the vowels contained.
   
   
   2. Increment the count on the indicated bin.
   
   
   
   


2. For every vowel:
   
   
   
   
   1. Iterate the bins containing words with that vowel.
   
   
   2. Add the count to the respective bin without that vowel.
   
   
   
   


3. For all bins:
   Multiply the count in the bin with the count in the complementary bin, and add that.


4. Subtract twice the count in the bin for words containing all vowels. Those account for all self-pairings.


5. The answer is half the calculated number, as we counted double.

Exercise for the attentive reader: Save half the multiplications this algorithm uses.