# 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. – Incomputable 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