Skip to content

647. Palindromic Substrings

Description

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Solutions

Solution 1: Expand Around Center

Thinking

Count palindromic substrings. A full \(n^2\) DP table works but is unnecessary if we only need the count.

Expand around \(2n-1\) centers (odd and even) and increment once for every successful step.

We can enumerate the center position of each palindrome and expand outward to count the number of palindromic substrings. For a string of length \(n\), there are \(2n-1\) possible center positions (covering both odd-length and even-length palindromes). For each center, we expand outward until the palindrome condition is no longer satisfied, and count the number of palindromic substrings.

The time complexity is \(O(n^2)\), where \(n\) is the length of string \(s\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def countSubstrings(self, s: str) -> int:
        ans, n = 0, len(s)
        for k in range(n * 2 - 1):
            i, j = k // 2, (k + 1) // 2
            while ~i and j < n and s[i] == s[j]:
                ans += 1
                i, j = i - 1, j + 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int n = s.length();
        for (int k = 0; k < n * 2 - 1; ++k) {
            int i = k / 2, j = (k + 1) / 2;
            while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
                ++ans;
                --i;
                ++j;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        int n = s.size();
        for (int k = 0; k < n * 2 - 1; ++k) {
            int i = k / 2, j = (k + 1) / 2;
            while (~i && j < n && s[i] == s[j]) {
                ++ans;
                --i;
                ++j;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func countSubstrings(s string) int {
    ans, n := 0, len(s)
    for k := 0; k < n*2-1; k++ {
        i, j := k/2, (k+1)/2
        for i >= 0 && j < n && s[i] == s[j] {
            ans++
            i, j = i-1, j+1
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
    let ans = 0;
    const n = s.length;
    for (let k = 0; k < n * 2 - 1; ++k) {
        let i = k >> 1;
        let j = (k + 1) >> 1;
        while (~i && j < n && s[i] == s[j]) {
            ++ans;
            --i;
            ++j;
        }
    }
    return ans;
};

Solution 2: Manacher's Algorithm

Thinking

Center expansion is \(O(n^2)\) in the worst case. Manacher computes every arm length \(p[i]\) in linear time after inserting separators; the center contributes \(\lfloor p[i]/2\rfloor\) palindromes.

In Manacher's algorithm, \(p[i] - 1\) represents the maximum palindrome length centered at position \(i\), and the number of palindromic substrings centered at position \(i\) is \(\left \lceil \frac{p[i]-1}{2} \right \rceil\).

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def countSubstrings(self, s: str) -> int:
        t = '^#' + '#'.join(s) + '#$'
        n = len(t)
        p = [0 for _ in range(n)]
        pos, maxRight = 0, 0
        ans = 0
        for i in range(1, n - 1):
            p[i] = min(maxRight - i, p[2 * pos - i]) if maxRight > i else 1
            while t[i - p[i]] == t[i + p[i]]:
                p[i] += 1
            if i + p[i] > maxRight:
                maxRight = i + p[i]
                pos = i
            ans += p[i] // 2
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int countSubstrings(String s) {
        StringBuilder sb = new StringBuilder("^#");
        for (char ch : s.toCharArray()) {
            sb.append(ch).append('#');
        }
        String t = sb.append('$').toString();
        int n = t.length();
        int[] p = new int[n];
        int pos = 0, maxRight = 0;
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            p[i] = maxRight > i ? Math.min(maxRight - i, p[2 * pos - i]) : 1;
            while (t.charAt(i - p[i]) == t.charAt(i + p[i])) {
                p[i]++;
            }
            if (i + p[i] > maxRight) {
                maxRight = i + p[i];
                pos = i;
            }
            ans += p[i] / 2;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int countSubstrings(string s) {
        string t = "^#";
        for (char c : s) {
            t += c;
            t += '#';
        }
        t += "$";

        int n = t.size();
        vector<int> p(n, 0);
        int pos = 0, maxRight = 0;
        int ans = 0;

        for (int i = 1; i < n - 1; ++i) {
            if (maxRight > i) {
                p[i] = min(maxRight - i, p[2 * pos - i]);
            } else {
                p[i] = 1;
            }

            while (t[i - p[i]] == t[i + p[i]]) {
                ++p[i];
            }

            if (i + p[i] > maxRight) {
                maxRight = i + p[i];
                pos = i;
            }

            ans += p[i] / 2;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func countSubstrings(s string) int {
    t := "^#"
    for _, c := range s {
        t += string(c)
        t += "#"
    }
    t += "$"

    n := len(t)
    p := make([]int, n)
    pos, maxRight := 0, 0
    ans := 0

    for i := 1; i < n-1; i++ {
        if maxRight > i {
            mirror := 2*pos - i
            if p[mirror] < maxRight-i {
                p[i] = p[mirror]
            } else {
                p[i] = maxRight - i
            }
        } else {
            p[i] = 1
        }

        for t[i-p[i]] == t[i+p[i]] {
            p[i]++
        }

        if i+p[i] > maxRight {
            maxRight = i + p[i]
            pos = i
        }

        ans += p[i] / 2
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function countSubstrings(s: string): number {
    let t = '^#';
    for (const c of s) {
        t += c + '#';
    }
    t += '$';

    const n = t.length;
    const p: number[] = new Array(n).fill(0);
    let pos = 0,
        maxRight = 0;
    let ans = 0;

    for (let i = 1; i < n - 1; i++) {
        if (maxRight > i) {
            p[i] = Math.min(maxRight - i, p[2 * pos - i]);
        } else {
            p[i] = 1;
        }

        while (t[i - p[i]] === t[i + p[i]]) {
            p[i]++;
        }

        if (i + p[i] > maxRight) {
            maxRight = i + p[i];
            pos = i;
        }

        ans += Math.floor(p[i] / 2);
    }

    return ans;
}

Comments