647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

  1. The input string length won’t exceed 1000.

AC code

Approach #1

The easiest way to solve this question is to traverse the array with two pointers, one from left and the other from right. When the value of the two pointers equal, we can move them one by one to the center to see whether their value are still equal.

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = s.length
    for(let i=0;i<s.length-1;i++){
        for(let j = s.length-1;j>i;j--){
            if(s[i]===s[j]){
                count += validateString(s,i,j)
            }
        }
    }
    return count;
};

function validateString (str,start,end){
    let i = start, j = end
    while(i<j){
        if(str[i]!==str[j]){
            return 0
        }
        i++
        j--
    }
    return 1
} 

Complexity Analysis

  • Time Complexity: O(N^2)
  • Space Complexity: O(1).

Approach #2: Expand Around Center

Assume each letter to be center of the palindromic substrings. For each center, let’s count all the palindromes that have this center. Notice that if [a, b] is a palindromic interval (meaning S[a], S[a+1], …, S[b] is a palindrome), then [a+1, b-1] is one too.

For each possible palindrome center, let’s expand our candidate palindrome on the interval [left, right] as long as we can. The condition for expanding is left >= 0 and right < N and S[left] == S[right]. That means we want to count a new palindrome S[left], S[left+1], …, S[right].

Approach #3: Manacher’s Algorithm

Intuition

Manacher’s algorithm is a textbook algorithm that finds in linear time, the maximum size palindrome for any possible palindrome center. If we had such an algorithm, finding the answer is straightforward.

What follows is a discussion of why this algorithm works.

Algorithm

Our loop invariants will be that center, right is our knowledge of the palindrome with the largest right-most boundary with center < i, centered at center with right-boundary right. Also, i > center, and we’ve already computed all Z[j]’s for j < i.

When i < right, we reflect i about center to be at some coordinate j = 2 * center - i. Then, limited to the interval with radius right - i and center i, the situation for Z[i] is the same as for Z[j].

For example, if at some time center = 7, right = 13, i = 10, then for a string like A = ‘@#A#B#A#A#B#A#’, thecenteris at the‘#’between the two middle‘A’'s, the right boundary is at the last‘#’,iis at the last‘B’, andjis at the first‘B’. Notice that limited to the interval[center - (right - center), right](the interval with centercenterand right-boundaryright), the situation foriandjis a reflection of something we have already computed. Since we already knowZ[j] = 3, we can quickly findZ[i] = min(right - i, Z[j]) = 3. Now, why is this algorithm linear? The while loop only checks the condition more than once whenZ[i] = right - i. In that case, for each timeZ[i] += 1, it incrementsright, andrightcan only be incremented up to2*N+2times. Finally, we sum up(v+1) / 2for eachv in Z. Say the longest palindrome with some given center C has radius R. Then, the substring with center C and radius R-1, R-2, R-3, ..., 0 are also palindromes. Example:abcdedcbais a palindrome with centere, radius 4: bute,ded,cdedc,bcdedcb, andabcdedcbaare all palindromes. We are dividing by 2 because we were using half-lengths instead of lengths. For example we actually had the palindromea#b#c#d#e#d#c#b#a`, so our length is twice as big.

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  const array = s.split("");
  let n = 0,
    m = 0;
  for (let i = 0; i < array.length; i++) {
    if (array[i] === "*" || array[i] === "(") {
      n++;
    } else {
      n--;
    }
    if (n < 0) {
      return false;
    }
  }

  for (let i = array.length - 1; i >= 0; i--) {
    if (array[i] === "*" || array[i] === ")") {
      m++;
    } else {
      m--;
    }
    if (m < 0) {
      return false;
    }
  }

  return true;
};

Complexity Analysis

  • Time Complexity: O(N),
  • Space Complexity: O(N).