4
\$\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\$
1
  • \$\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\$ Aug 29, 2017 at 10:22

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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