Skip to content

2472. Maximum Number of Non-overlapping Palindrome Substrings 👍

  • Time: $O(nk)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int maxPalindromes(string s, int k) {
    const int n = s.length();
    // dp[i] := the maximum number of substrings in the first i chars of s
    vector<int> dp(n + 1);

    // If a palindrome is a substring of another palindrome, then considering
    // the longer palindrome won't increase the number of non-overlapping
    // palindromes. So, we only need to consider the shorter one. Also,
    // considering palindromes with both k length and k + 1 length ensures that
    // we look for both even and odd length palindromes.
    for (int i = k; i <= n; ++i) {
      dp[i] = dp[i - 1];
      // Consider palindrome with length k.
      if (isPalindrome(s, i - k, i - 1))
        dp[i] = max(dp[i], 1 + dp[i - k]);
      // Consider palindrome with length k + 1.
      if (isPalindrome(s, i - k - 1, i - 1))
        dp[i] = max(dp[i], 1 + dp[i - k - 1]);
    }

    return dp[n];
  }

 private:
  // Returns true is s[i..j) is a palindrome.
  bool isPalindrome(const string& s, int l, int r) {
    if (l < 0)
      return false;
    while (l < r)
      if (s[l++] != s[r--])
        return false;
    return true;
  }
};

 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
class Solution {
  public int maxPalindromes(String s, int k) {
    final int n = s.length();
    // dp[i] := the maximum number of substrings in the first i chars of s
    int[] dp = new int[n + 1];

    // If a palindrome is a subString of another palindrome, then considering
    // the longer palindrome won't increase the number of non-overlapping
    // palindromes. So, we only need to consider the shorter one. Also,
    // considering palindromes with both k length and k + 1 length ensures that
    // we look for both even and odd length palindromes.
    for (int i = k; i <= n; ++i) {
      dp[i] = dp[i - 1];
      // Consider palindrome with length k.
      if (isPalindrome(s, i - k, i - 1))
        dp[i] = Math.max(dp[i], 1 + dp[i - k]);
      // Consider palindrome with length k + 1.
      if (isPalindrome(s, i - k - 1, i - 1))
        dp[i] = Math.max(dp[i], 1 + dp[i - k - 1]);
    }

    return dp[n];
  }

  // Returns true is s[i..j) is a palindrome.
  private boolean isPalindrome(String s, int l, int r) {
    if (l < 0)
      return false;
    while (l < r)
      if (s.charAt(l++) != s.charAt(r--))
        return false;
    return true;
  }
}

 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
class Solution:
  def maxPalindromes(self, s: str, k: int) -> int:
    n = len(s)
    # dp[i] := the maximum number of substrings in the first i chars of s
    dp = [0] * (n + 1)

    def isPalindrome(l: int, r: int) -> bool:
      """Returns True is s[i..j) is a palindrome."""
      if l < 0:
        return False
      while l < r:
        if s[l] != s[r]:
          return False
        l += 1
        r -= 1
      return True

    # If a palindrome is a subof another palindrome, then considering
    # the longer palindrome won't increase the number of non-overlapping
    # palindromes. So, we only need to consider the shorter one. Also,
    # considering palindromes with both k length and k + 1 length ensures that
    # we look for both even and odd length palindromes.
    for i in range(k, n + 1):
      dp[i] = dp[i - 1]
      # Consider palindrome with length k.
      if isPalindrome(i - k, i - 1):
        dp[i] = max(dp[i], 1 + dp[i - k])
      # Consider palindrome with length k + 1.
      if isPalindrome(i - k - 1, i - 1):
        dp[i] = max(dp[i], 1 + dp[i - k - 1])

    return dp[n]