3
\$\begingroup\$

This Problem is from https://www.codechef.com/problems/PRINCESS .

The Problem in brief - i am given a string of length N. I have to check among all the the substrings that whether a substring exist or not which is palindrome and having length greater than 1. If such a substring exists then print YES else print NO.

Input The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing a string.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 100000

Subtasks

Subtask #1 (20 points), Time limit : 1 sec 1 ≤ T<=10, N<=1000

Subtask #2 (80 points), Time limit : 1 sec 1 ≤ T<=10, N<=100000

How Do I optimize the code? I am getting subtask #1 right , with this code.

int main()
{
    int T;
    string s,sub;
    int n,counter;
    int i,j,k;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
        cin>>s;
        n = s.length();
        counter=0;

        for(j=0;j<n-1;j++)
        {
          if(counter==1)
                    break;
                for(k=2;k+j<=n;k++)
                {
                   sub=s.substr(j,k);
                    if( equal(sub.begin(), sub.begin() + sub.size()/2, sub.rbegin()) )
                    {
                        counter++;
                        break;
                    }
                }
        }
        if(counter==0)
                printf("NO\n");
        else
                 printf("YES\n");
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I believe there is an algorithm which finds all palindromes in linear time. That would certainly get you through the next subtask. Try to google for it. \$\endgroup\$ – Incomputable Aug 29 '17 at 10:22
6
\$\begingroup\$

There's a simple linear solution.

You don't have to check all substrings. If an [l, r] substring is a palindrome and r - l > 2, so is [l + 1, r - 1]. Thus, it's sufficient to check only substrings of length 2 and 3.

One can do with a single pass over the input string:

for i in [0 .. s.length() - 2]:
     if s[i] == s[i + 1]:
         return true
     if i != 0 and s[i - 1] == s[i + 1]:
         return true
return false
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.