I tried implementing the logic stated in the editorial of SECPASS, but got WA?

general
, ,
1

Here is the editorial for SECPASS problem https://discuss.codechef.com/questions/145624/secpass-editorial

Here is my solution https://www.codechef.com/viewsolution/23147320

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
    int n,countn=0;
    cin>>n;
    string s,ans;
    cin>>s;
    char first = s[0];
    countn = count(s.begin(),s.end(),first);
    if(countn>1){
        ans = s[0];
        for(int i=1,j=s.find(first,1)+1;j<n;i++,j++){
            if(s[i]==s[j]){
                ans+=s[i];
            }
            else{
                break;
            }
        }
    }
    if(countn==1){
        cout<<s<<endl;
    }
    else{
        cout<<ans<<endl;
    }
}
}

Can you please tell what is wrong in the code or provide the correct code if wrong?

2

Hi @mohitmm

According to the question, you have to give the prefix which has occurred the most number of times and if there are two prefixes of the same count, you have to output the biggest one.
I think your code isn’t working because you are only taking the 2nd occurrence of the first letter (s[0]) and checking it with the first few letters of the string one by one.

Instead, you must start with the biggest substring till the second occurrence of the first letter (not including it) and get the count of that substring with the whole string and see if it matches n//countn.

Eg: Take the string ‘THYTH’. Get the first letter count, which is 2. Divide that with the total letters, which is 5//2=2. Start from s[0…2]=‘TH’. Get the count of ‘TH’ in the string, which is 2. This matches our previous floor division value. Hence, ‘TH’ is the required prefix. If it doesn’t match, go to s[0…1] and so on.

I hope I have cleared your doubt. Since, I don’t code C++, please check my Python implementation

Cheers
Aadarsh…

3

@aadarsh_ram , Thanks man. The problem with my code was that I was not tracking all the occurrence of a 1st character in the string for getting the biggest string. Here is the passed solution: https://www.codechef.com/viewsolution/23171960

4

Glad to know that you got AC, @mohitmm. Thanks.