g2401_2500.s2472_maximum_number_of_non_overlapping_palindrome_substrings

Class Solution

java.lang.Object

g2401_2500.s2472_maximum_number_of_non_overlapping_palindrome_substrings.Solution

public class Solution
extends Object

2472 - Maximum Number of Non-overlapping Palindrome Substrings.

Hard

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 = “ aba cc dbbd ”. 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.

Constructor Summary

Constructors

Constructor and Description
Solution()

Method Summary

Modifier and Type	Method and Description
int	maxPalindromes(String s, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Solution

public Solution()

Method Detail

maxPalindromes

public int maxPalindromes(String s,
                          int k)