Unique prefix for array of strings

#1

plz provide the code for this problem using tries…and also include the case where we can have no unique prefix as
well in the code

#2

@S19LPPP0202
Here is the code


No unique prefix will only be in the case when you have 2 exact same strings in input

#3

ok is there any other efficient approach than this??
what is time and space complexity of this approach…

#4

@S19LPPP0202
Your approach is perfect with best time complexity

TC - O( N * K ) where K can be assumed to be max length among all strings
SC - O( N * K ) because in worst case all strings can be of length K with different characters

If your doubt is resolved please close it

#5

this doubt is related to the codechef lunchtime april 2020 div 2 problem another bithday present…
i have used the following approach but it is showing wrong answer…
plz tell me what is wromg in my logic and dont forward the link of editorial of the problems given on codechef site…
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int divisor(int n,int k)
{
if(n==1&&k!=1)
{
return 0;
}
if(n%k==0)
{
return 1;
}
return 0;
}
int32_t main() {
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int a[n];
vectorv,v2;
for(int i=0;i<n;i++)
{
cin>>a[i];
v.push_back(a[i]);
}
sort(v.begin(),v.end());

    int z=0;
    for(int i=0;i<n;i++)
    {
        if(v[i]!=a[i])
        {
            v2.push_back(i);
            z=1;
        }
    }
    if(z!=1)
    {
        cout<<"yes"<<"\n";
    }
    else 
    {
        
        int x=v2[0];
        for(int i=1;i<v2.size();i++)
        {
            if(divisor(abs(v2[i]-x),k)==0)
            {
                cout<<"no"<<"\n";
                z=0;
                break;
            }
            x=v2[i];
        }
        if(z!=0)
        {
            cout<<"yes"<<"\n";
        }
    }
}

}
plz tell what is wrong in this approach and also testcases where this approach fails…

#6

Hey @S19LPPP0202
Please don’t pile up different doubts on same doubt
It becomes difficult to manage doubts this way
I request you to open a new doubt for this query
Hope you understand
Thanks

#7


This is the link plz reply I have asked this question…

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.