回文串算法题解

5. 最长回文子串

动态规划解法

复杂度 $O(n^2)$，令 dp[i][j] 表示 s[i:j+1] 是否是回文子串，则：

• dp[i][i] = True
• j-i == 1时，dp[i][j] = s[i] == s[j]
• j-1 > 1 且 s[i] == s[j] 时 dp[i][j] = dp[i+1][j-1]

当 dp[i][j] == True 时，更新最长回文子串。

因为状态转移函数是 dp[i][j] = dp[i+1][j-1]，所以要求第一层 i 循环是逆序遍历

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False]*len(s) for _ in range(len(s))]
        max_s = ''

        for i in reversed(range(len(s))):
            for j in range(i,len(s)):
                if i == j:
                    dp[i][j] = True
                elif j-i == 1:
                    dp[i][j] = s[j] == s[i]
                elif s[j] == s[i]:
                    dp[i][j] = dp[i+1][j-1]

                if dp[i][j]:
                    max_s = max(s[i:j+1],max_s,key=len)
        return max_s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

压缩条件

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False]*len(s) for _ in range(len(s))]
        max_s = ''

        for i in reversed(range(len(s))):
            for j in range(i,len(s)):
                if (i== j) or (s[i] == s[j] and (j-i == 1 or dp[i+1][j-1])):
                    dp[i][j] = True
                    max_s = max(s[i:j+1],max_s,key=len)

        return max_s
1
2
3
4
5
6
7
8
9
10
11
12

压缩空间

class Solution:
    def longestPalindrome(self, s: str) -> str:

        max_s = ''

        f = [False]*len(s)
        for i in reversed(range(len(s))):
            dp = [False]*len(s)
            for j in range(i,len(s)):
                if (i== j) or (s[i] == s[j] and (j-i == 1 or f[j-1])):
                    dp[j] = True
                    max_s = max(s[i:j+1],max_s,key=len)
            f = dp
        return max_s
1
2
3
4
5
6
7
8
9
10
11
12
13
14

647. 回文子串 也可以顺便捞走

647. 回文子串

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0

        f = [False]*len(s)
        for i in reversed(range(len(s))):
            dp = [False]*len(s)
            for j in range(i,len(s)):
                if (i== j) or (s[i] == s[j] and (j-i == 1 or f[j-1])):
                    dp[j] = True
                    ans += 1
            f = dp

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

中心扩展法

中心扩展法是枚举每一个可能的回文中心，对每个回文中心，用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

可以假设字符串中间有间隙，则 n 个字符共有 2n-1 个回文中心（n 个奇数中心，n-1个偶数中心）

a#b#c#b#c
n=5 时，共有 2n-1 个回文中心
1
2

可以分两遍遍历，第一遍奇数中心，第二遍偶数中心

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i in range(n):
            # 奇数中心，n次
            l = r = i
            while l>=0 and r<len(s) and s[l] == s[r]:
                l-=1
                r+=1
                ans += 1
            # 偶数中心
            l=i
            r=i+1 # 根据边界条件会少遍历一遍，即 n-1
            while l>=0 and r<len(s) and s[l] == s[r]:
                l-=1
                r+=1
                ans +=1

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

当合并两次遍历时，可以通过找规律发现 l 和 r 对应 i 的值：

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i in range(2*n-1):
            l = i // 2
            r = i // 2 + i % 2
            while l>=0 and r<len(s) and s[l] == s[r]:
                l-=1
                r+=1
                ans += 1

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

Manacher 算法

Manacher 的思想基于中心扩展法。假设已得到一个回文子串 s,回文中心为 i，则在该回文中心右侧的下标 j(j>i)，可以复用对称侧的信息，避免直接以 j 为中心进行扩展，这是 Manacher 算法的核心思想，从而实现了近似一遍遍历的复杂度。

... c b c b c b
... 1 3 5
          3(该中心的回文长度至少为 3)
      |___|
    |_______|
      历史能到达的最长回文子串
1
2
3
4
5
6

算法在实现过程中维护了历史遍历中回文子串能到达的最右边界下标 jr 和该最右边界对应的回文子串的回文中心 j，此时，对于当前遍历下标 i：

• 如果 i > jr，说明历史信息不可用，此时仍然按中心扩展法的思路处理
• 如果 i <= jr，此时 j 是 jr 对应的回文中心，假设 il 是以 j 为中心 i 的左侧对称点，因为 i+il == 2*j，可得 il = 2*j-i，此时：
  • dp[il] 可能大于 dp[j]，因为更新原则，此时 il+dp[il] < j+dp[j] and il < j，此时初始化 dp[i] 不能按照 dp[il] 的值初始化，因为可能会无效，因此可以初始化 dp[i] = rj-i（i 到子串边界的长度）
  • 否则，dp[i] = dp[il]
• 最后，对于任意长度为 n 的回文串，保证中心不变的情况下，一共可以得到 (n+1)//2 个回文子串。
• 在本题的处理中，dp[i] 存储的是最大回文半径，但因为字符串之间都插入了 #，按照下面两个推论，用 ans += (dp[i]+1)//2 更新即可
  • s[i] == # 表示回文串长度是偶数，回文子串数量为 dp[i]//2 == (dp[i]+1)//2
  • s[i] != # 表示回文串长度是奇数，回文子串数量为 (dp[i]+1)//2 == dp[i]//2+1

n=5, n//2=2
abcba
 bcb
  c

n=4, n//2=2
abba
 bb
1
2
3
4
5
6
7
8

class Solution:
    def countSubstrings(self, s: str) -> int:
        s = ''.join(['$#', '#'.join(s), '#!'])
        n = len(s)
        dp = [0] * n

        # jr: 回文子串能到达的最右侧下标
        # j: jr 对应的回文子串的回文中心
        j = jr = 0
        ans = 0
        for i in range(2, n - 2):
            # i 被包含在当前最大回文子串内(right与当前点的距离, i关于j对称的点的f值)，不被包含(0)
            # 这里将 right−i 和 f[对称点] 取小，是先要保证这个回文串在当前最大回文串内。
            dp[i] = min(jr - i, dp[2 * j - i]) if i <= jr else 0
            while s[i + dp[i] + 1] == s[i - dp[i] - 1]:
                dp[i] += 1

            if i + dp[i] > jr:
                j = i
                jr = i + dp[i]

            ans += (dp[i] + 1) // 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

具体的实现思路：

• 将偶数中心通过在字符间（包括两边）添加违禁字符 # 的方式处理成奇数中心
• 将 dp[i] 定义为以 i 为奇数中心的最大回文半径，dp[i]-1 为以 i 为中心的真实的回文长度（如下图所示）
• 为了边界判断，在两侧再添加 $ 和 ^ 保证两边字符不等

$ # c # b # c # b # c # c # d # e # ^
0 0 1 0 3 0 5 0 3 0 1 2 1 0 1 0 1 0 0
1
2

class Solution:
    def countSubstrings(self, s: str) -> int:
        s = ''.join(['$#', '#'.join(s), '#!'])
        n = len(s)
        dp = [0] * n

        # jr: 回文子串能到达的最右侧下标
        # j: jr 对应的回文子串的回文中心
        j = jr = 0
        ans = 0
        for i in range(2, n - 2):
            # i 被包含在当前最大回文子串内(right与当前点的距离, i关于j对称的点的f值)，不被包含(0)
            # 这里将 right−i 和 f[对称点] 取小，是先要保证这个回文串在当前最大回文串内。
            dp[i] = min(jr - i, dp[2 * j - i]) if i <= jr else 0
            while s[i + dp[i] + 1] == s[i - dp[i] - 1]:
                dp[i] += 1

            if i + dp[i] > jr:
                j = i
                jr = i + dp[i]

            ans += (dp[i] + 1) // 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

6236. 不重叠回文子字符串的最大数目

主要逻辑：

• 对每个回文中心，用中心扩展法（或 Manacher 法）得到回文子串的左右边界为 l,r，对每个 r-l+1 >= k （符合题目要求）的子串，用贪心算法更新最大数量
• 令 f[i] 为到 s[:i] 的最大数目，则 f[r] = max(f[r],f[l-1]+1)，f[i] = max(f[i-1],f[i])

class Solution:
    def maxPalindromes(self, s: str, k: int) -> int:
        n = len(s)
        f = [0] * (n)
        for i in range(n):
            # 初始化，不需要边界判断（f[-1] == 0）
            f[i] = max(f[i - 1], f[i])

            # 奇数长子串
            l = r = i
            while l>=0 and r<n and s[l] == s[r]:
                # 贪心判断，不需要更长的
                if r-l+1 >= k:
                    f[r] = max(f[l-1]+1,f[r])
                    break
                l -= 1
                r += 1

            # 偶数长子串
            l = i
            r = i+1
            while l>=0 and r<n and s[l] == s[r]:
                if r-l+1 >= k:
                    f[r] = max(f[l-1]+1,f[r])
                    break
                l-=1
                r+=1

        return f[-1]
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