Special Palindrome Again

A string is said to be a special palindromic string if either of two conditions is met:

• All of the characters are the same, e.g. aaa.
• All characters except the middle one are the same, e.g. aadaa.

A special palindromic substring is any substring of a string which meets one of those criteria. Given a string, determine how many special palindromic substrings can be formed from it.

For example, given the string , we have the following special palindromic substrings:.

Function Description

Complete the substrCount function in the editor below. It should return an integer representing the number of special palindromic substrings that can be formed from the given string.

substrCount has the following parameter(s):

• n: an integer, the length of string s
• s: a string

Input Format

The first line contains an integer, , the length of . 
The second line contains the string .

Constraints

 
Each character of the string is a lowercase alphabet, .

Output Format

Print a single line containing the count of total special palindromic substrings.

Sample Input 0

5
asasd

Sample Output 0

7 

Explanation 0

The special palindromic substrings of  are 

Sample Input 1

7
abcbaba

Sample Output 1

10 

Explanation 1

The special palindromic substrings of  are 

Sample Input 2

4
aaaa

Sample Output 2

10

Explanation 2

The special palindromic substrings of  are 

---

이 문제의 기본은 palindrome 문자열을 약간 변형한(Special) 문자열의 갯수를 찾는 문제이다. 

기본적으로 palindrome 문자열은 앞/뒤 대칭이 같은 문자열이다. 즉, aaoaa, aboba 와 같이 중앙을 기준으로 같은 문자열이 대칭인 상태를 얘기한다.

문제는.......기본적인 알고리즘으로 작성을 하게 되면 역시나 타임아웃으로 테스트 케이스를 통과하지 못한다. 아주 속이 터진다....ㅠ

첫번째 기본 알고리즘으로 작성한 코드는 다음과 같다.

위 코드는 기본적인 테스트 케이스는 통과하지만, 아주 긴 문자열에서는 꼭 타임아웃이 발생한다. ㅠㅠ 도대체 타임아웃의 기준이 뭔지 모르겠다.

어쨋든 그래서 다른 로직으로 작성해보았다. 두번째 코드이다.

가운데를 기준으로 좌,우의 문자열을 떼어내서 그게 같은지 다른지 확인하는 로직이다.

이 로직도 결국 긴 문자열에서는 타임아웃이 발생한다. 아후.........

결국 Discussion의 내용을 검토하여 최종 로직을 작성하였다.

아직 위 로직이 어떤 원리로 처리되었는지 이해가 잘 되진 않는다.......다시 제대로 꼼꼼히 따져서 확인해봐야겠다. ㅠ