Question

2472. Maximum Number of Non-overlapping Palindrome Substrings

中文文档

Description

You are given a string s and a positive integer k.

Select a set of non-overlapping substrings from the string s that satisfy the following conditions:

• The length of each substring is at least k.
• Each substring is a palindrome.

Return _the maximum number of substrings in an optimal selection_.

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

 

Example 1:

Input: s = "abaccdbbd", k = 3
Output: 2
Explanation: We can select the substrings underlined in s = "abaccdbbd". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.

Example 2:

Input: s = "adbcda", k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.

 

Constraints:

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

Solutions

Solution 1: Preprocessing + Memoization Search

First, preprocess the string $s$ to get $dp[i][j]$, which represents whether the substring $s[i,..j]$ is a palindrome.

Then, define a function $dfs(i)$ to represent the maximum number of non-overlapping palindrome substrings that can be selected from the substring $s[i,..]$, i.e.,

$$ \begin{aligned} dfs(i) &= \begin{cases} 0, & i \geq n \ \max{dfs(i + 1), \max_{j \geq i + k - 1} {dfs(j + 1) + 1}}, & i < n \end{cases} \end{aligned} $$

The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the string $s$.

class Solution:
  def maxPalindromes(self, s: str, k: int) -> int:
    @cache
    def dfs(i):
      if i >= n:
        return 0
      ans = dfs(i + 1)
      for j in range(i + k - 1, n):
        if dp[i][j]:
          ans = max(ans, 1 + dfs(j + 1))
      return ans

    n = len(s)
    dp = [[True] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
      for j in range(i + 1, n):
        dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
    ans = dfs(0)
    dfs.cache_clear()
    return ans

class Solution {
  private boolean[][] dp;
  private int[] f;
  private String s;
  private int n;
  private int k;

  public int maxPalindromes(String s, int k) {
    n = s.length();
    f = new int[n];
    this.s = s;
    this.k = k;
    dp = new boolean[n][n];
    for (int i = 0; i < n; ++i) {
      Arrays.fill(dp[i], true);
      f[i] = -1;
    }
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
      }
    }
    return dfs(0);
  }

  private int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != -1) {
      return f[i];
    }
    int ans = dfs(i + 1);
    for (int j = i + k - 1; j < n; ++j) {
      if (dp[i][j]) {
        ans = Math.max(ans, 1 + dfs(j + 1));
      }
    }
    f[i] = ans;
    return ans;
  }
}

class Solution {
public:
  int maxPalindromes(string s, int k) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, true));
    vector<int> f(n, -1);
    for (int i = n - 1; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];
      }
    }
    function<int(int)> dfs = [&](int i) -> int {
      if (i >= n) return 0;
      if (f[i] != -1) return f[i];
      int ans = dfs(i + 1);
      for (int j = i + k - 1; j < n; ++j) {
        if (dp[i][j]) {
          ans = max(ans, 1 + dfs(j + 1));
        }
      }
      f[i] = ans;
      return ans;
    };
    return dfs(0);
  }
};

func maxPalindromes(s string, k int) int {
  n := len(s)
  dp := make([][]bool, n)
  f := make([]int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]bool, n)
    f[i] = -1
    for j := 0; j < n; j++ {
      dp[i][j] = true
    }
  }
  for i := n - 1; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
    }
  }
  var dfs func(int) int
  dfs = func(i int) int {
    if i >= n {
      return 0
    }
    if f[i] != -1 {
      return f[i]
    }
    ans := dfs(i + 1)
    for j := i + k - 1; j < n; j++ {
      if dp[i][j] {
        ans = max(ans, 1+dfs(j+1))
      }
    }
    f[i] = ans
    return ans
  }
  return dfs(0)
}