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: Dynamic Programming

• Time complexity: O(nk)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const maxPalindromes = function (s, k) {
  const n = s.length;
  const dp = Array.from({ length: n + 1 }, () => 0);

  const isPalindrome = (left, right) => {
    if (left < 0) return false;

    while (left < right) {
      if (s[left] !== s[right]) return false;

      left += 1;
      right -= 1;
    }

    return true;
  };

  for (let index = k; index <= n; index++) {
    dp[index] = dp[index - 1];

    if (isPalindrome(index - k, index - 1)) {
      const len = 1 + dp[index - k];

      dp[index] = Math.max(len, dp[index]);
    }

    if (isPalindrome(index - k - 1, index - 1)) {
      const len = 1 + dp[index - k - 1];

      dp[index] = Math.max(len, dp[index]);
    }
  }

  return dp[n];
};