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

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