647. Palindromic Substrings

Problem

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.

https://leetcode.com/problems/palindromic-substrings/

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.

Test Cases

1 2	class Solution: def countSubstrings(self, s: str) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ('abc', 3),
    ('aaa', 6),
])
class Test:
    def test_solution(self, s, expected):
        sol = Solution()
        assert sol.countSubstrings(s) == expected

Thoughts

这个跟 5. Longest Palindromic Substring 的处理逻辑几乎一致。

区别就是那个问题只记录最长的回文长度，而这个问题需要记录见到的所有回文的数量。

同样是从左到右遍历每个字符，对于当前字符，检查以其为中心能够构成的 palindromic 数量。

计数的时候注意，一个回文去掉首尾字符后的子回文也算一个。

Code

solution.py

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)

        def count_palindromic(mid, odd):
            l, r = mid - (odd and 1 or 0), mid + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l, r = l - 1, r + 1

            # For a 2k-1 length odd palindromic, counting as k.
            # For a 2k length even palindromic, counting as k.
            # Here the palindromic length is r - l - 1.
            # If r - l - 1 is odd, k = (r - l) / 2.
            # If r - l - 1 is even, k = (r - l - 1) / 2 = (r - l) // 2.
            return (r - l) >> 1

        count = 0
        for i in range(n):
            # Check longest odd palindromic substring where s[i] is middle.
            count += count_palindromic(i, True)
            # Check longest even palindromic substring where s[i] and s[i+1] together are middle.
            count += count_palindromic(i, False)

        return count

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。