subanagr confusion

general
1

Please refer to this problem…

I interpreted this question that we have to found the characters that are present in all the given set of strings… and display those in alpabetically sorted order…

Accordingly, I constructed solution like this:

#include
#include
#include<math.h>
#include
#include
#include<string.h>
#include<ctype.h>

#define mod 1000000007
#define ll long long
#define ull unsigned long long

using namespace std;

int main()
{

int flag,k,j,t,i,min=200;
string s[110],o,ans;

scanf("%d",&t);
    
for(i=0;i<t;i++)
{
    cin>>s[i];
    if(s[i].length()<min)
    {
        min=s[i].length();
        k=i;
    }
}
    o=s[k];
    
    for(j=0;o[j];j++)
    {
        flag=0;
        for(i=0;i<t;i++)
        {
            if(s[i].find_first_of(o[j])>101)
            {
             flag=1;
             break;
            }
            
        }
            if(flag==0)
            ans=ans+o[j];
    }
    
    sort(ans.begin(),ans.end());
    if(ans.length()==0)
    cout<<"no such string";
    cout<<ans;






return 0;

}

Where am I wrong? It is working for the test cases I am able to think of?
2

Your logic for the solution is correct, however there is a bug in your program. Consider the input

2
aa
ab

Your code gives output “aa” whereas the correct answer is “a”. If you dry run the program with this input, you’ll find o = “aa”, and consequently, searching through “ab” twice for the character ‘a’ finds the first ‘a’ both times. So your program believes wrongly that “ab” has 2 *‘a’*s.

A simple remedy to this is to set an already counted character to an non lowercase alphabet character so it does not get counted again. Consider replacing your inner loop with this

for(i=0; i<t; i++){
    k = s[i].find_first_of(o[j]);
    if(k==string::npos){
        flag=1;
        break;
    }
    else
        s[i][k] = '*'; //or any other non lowercase alphabet character
}

Although this is enough to get AC, this is quite an inefficient approach, O(mn^2) to be precise where m is the number of strings and n is the maximum length of a string. An O(mn) solution is possible if you make character frequency arrays out of the strings and use them instead. Take a look at this neat solution by udittidu. I hope this solves your problem!

1 Like
3

I couldn’t locate this bug yesterday while I was attempting this problem, but strangely when I woke up today, the first thoughts that were floating in my mind were regarding this problem. and the bug just striked me even when I wasn’t not yet completely awake… And, I corrected it to get AC.

Thanks for pointing to the better solution. And, thanks for giving time to the problem.

4

@pankajkhan No problem, and I have experienced that too :slight_smile:
Do accept the answer as correct, thanks!