Palindrome from all the substrings

Question

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;
}

• Incomputable: 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.

Answer 1

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