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