COUNTPALIN

이 문제를 풀었습니다.

그러나 시간초과가 뜨네요...
DP를 활용한 문제라고 해서 풀어보려고 헀지만
어느 포인트에서 DP를 나타내야 하는지 잘 모르겠습니다...

아래는 제가 작성한 코드입니다.

a b b a 로 설명을 해보겠습니다.

첫번째 while문은
연속하는 문자열 (예를들면 b와 b)
이 같을 경우 count를 올립니다.
그런후 leftIndex와 rightIndex의 간격을 넓혀
또 똑같으면 count 를 올리는 방식입니다.

두번째 while문은
a b c b a 로 설명을 해보면...
특정 위치를 기준으로 (예를들면 c)
좌측과 우측이 같으면 count를 올립니다.
그런후 leftIndex와 rightIndex의 간격을 넓여
같으면 첫번째 while과 같은 방식으로 count를 올리는 겁니다.

물론 이 방식은 속도라는 측면에선... 이중으로 반복이 들어가니 많이 느리겠네요...

검색을 해보니 맨체스터 알고리즘이라는 것이 있는걸 보았습니다.
하지만 전 그것도 이해가 잘 가질 않네요...

이 문제의 시간복잡도를 줄이는 방법은 뭐가 있을까요?

import java.util.Scanner;

public class Main {

static Scanner scan = new Scanner(System.in);

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int testCase = scan.nextInt();
    while(testCase > 0)
    {
        countPalin();
        testCase--;
    }
}

private static void countPalin() {
    // TODO Auto-generated method stub

    int num = scan.nextInt();
    String arr = scan.next();
    int count = 0;


    for(int i=0; i<num; i++)
    {
        int left = i;
        int right = i+1;


        int left2 = i+1;
        int right2 = i+1;


        while(left>=0 && right < arr.length())
        {
            if( arr.charAt(left) == arr.charAt(right) )
            {
                count++;

                left--;
                right++;


            }
            else
                break;
        }

        while(left2>0 && right2+1 < arr.length())
        {
            if(left2>0 && arr.charAt(left2-1) == arr.charAt(right2+1))
            {
                count++;

                left2--;
                right2++;
            }
            else
                break;

        }

}   

    System.out.println(count);

}

}