2472 LeetCode problem solution

LeetCode problem link: 2472. Maximum Number of Non-overlapping Palindrome Substrings

LeetCode 2472 problem description

Hard level problem.

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.

LeetCode 2472 problem: solution explanation

This problem can be solved using Dynamic Programming + Palindrome Checking. The key observation is that we only need to consider palindromes of length k or k + 1. If a longer palindrome exists, we can remove matching characters from both ends until its length becomes k or k + 1, without reducing the maximum number of non-overlapping palindromes we can select.

Here,

dp[end]

represents the maximum number of non-overlapping palindrome substrings that can be selected from the first end characters.

For every position, we have two choices. The first choice is to skip the current character and keep the previous result:

dp[end] = dp[end - 1];

The second choice is to check whether a palindrome of length k or k + 1 ends at the current position. If [start, end - 1] is a palindrome, we can select it:

dp[end] = max(dp[end], dp[start] + 1);

Since dp[start] only considers characters before the new palindrome starts, the selected substrings cannot overlap.

LeetCode 2472 problem: complexity

We process n positions and check at most two substrings at each position. Checking whether a substring is a palindrome takes up to O(k) time.

Time complexity: O(n * k)
Space complexity: O(n)

With n <= 2000, this is at most a few million character comparisons, which is completely acceptable.

Pattern: Dynamic Programming
Technique: Palindrome Checking / Interval Selection

LeetCode 2472 C++ solution

class Solution {
public:
  int maxPalindromes(string s, int k)
  {
    int n = s.size();

    vector<int> dp(n + 1, 0);

    for(int end = 1; end <= n; end++)
    {
      dp[end] = dp[end - 1];

      for(int len : {k, k + 1})
      {
        int start = end - len;

        if(start >= 0 && isPalindrome(s, start, end - 1))
          dp[end] = max(dp[end], dp[start] + 1);
      }
    }

    return dp[n];
  }

private:
  bool isPalindrome(const string& s, int left, int right)
  {
    while(left < right)
    {
      if(s[left] != s[right]) return false;

      left++;
      right--;
    }

    return true;
  }
};

LeetCode 2472 Java solution

class Solution {
  public int maxPalindromes(String s, int k) {
    int n = s.length();
    int[] dp = new int[n + 1];

    for(int end = 1; end <= n; end++) {
      dp[end] = dp[end - 1];

      for(int len : new int[]{k, k + 1}) {
        int start = end - len;

        if(start >= 0 && isPalindrome(s, start, end - 1)) {
          dp[end] = Math.max(dp[end], dp[start] + 1);
        }
      }
    }

    return dp[n];
  }

  private boolean isPalindrome(String s, int left, int right) {
    while(left < right) {
      if(s.charAt(left) != s.charAt(right))
        return false;

      left++;
      right--;
    }

    return true;
  }
}

LeetCode 2472 JavaScript solution

var maxPalindromes = function(s, k) {
  const n = s.length;
  const dp = new Array(n + 1).fill(0);

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

      left++;
      right--;
    }

    return true;
  };

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

    for(const len of [k, k + 1]) {
      const start = end - len;

      if(start >= 0 && isPalindrome(start, end - 1)) {
        dp[end] = Math.max(dp[end], dp[start] + 1);
      }
    }
  }

  return dp[n];
};

LeetCode 2472 TypeScript solution

function maxPalindromes(s: string, k: number): number {
  const n: number = s.length;
  const dp: number[] = new Array(n + 1).fill(0);

  const isPalindrome = (left: number, right: number): boolean => {
    while(left < right) {
      if(s[left] !== s[right])
        return false;

      left++;
      right--;
    }

    return true;
  };

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

    for(const len of [k, k + 1]) {
      const start = end - len;

      if(start >= 0 && isPalindrome(start, end - 1)) {
        dp[end] = Math.max(dp[end], dp[start] + 1);
      }
    }
  }

  return dp[n];
}

LeetCode 2472 Python solution

class Solution:
  def maxPalindromes(self, s: str, k: int) -> int:
    n = len(s)
    dp = [0] * (n + 1)

    def is_palindrome(left: int, right: int) -> bool:
      while left < right:
        if s[left] != s[right]:
          return False

        left += 1
        right -= 1

      return True

    for end in range(1, n + 1):
      dp[end] = dp[end - 1]

      for length in (k, k + 1):
        start = end - length

        if start >= 0 and is_palindrome(start, end - 1):
          dp[end] = max(dp[end], dp[start] + 1)

    return dp[n]