# Palindrome from all the substrings

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

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

• 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. Aug 29 '17 at 10:22

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