Package 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.<p>Hard</p> <p>You are given a string <code>s</code> and a <strong>positive</strong> integer <code>k</code>.</p> <p>Select a set of <strong>non-overlapping</strong> substrings from the string <code>s</code> that satisfy the following conditions:</p> <ul> <li>The <strong>length</strong> of each substring is <strong>at least</strong> <code>k</code>.</li> <li>Each substring is a <strong>palindrome</strong>.</li> </ul> <p>Return <em>the <strong>maximum</strong> number of substrings in an optimal selection</em>.</p> <p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> s = &ldquo;abaccdbbd&rdquo;, k = 3</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> We can select the substrings underlined in s = &ldquo;<ins> <strong>aba</strong> </ins>cc<ins> <strong>dbbd</strong> </ins>&rdquo;. Both &ldquo;aba&rdquo; and &ldquo;dbbd&rdquo; 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.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> s = &ldquo;adbcda&rdquo;, k = 2</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> There is no palindrome substring of length at least 2 in the string.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= k <= s.length <= 2000</code></li> <li><code>s</code> consists of lowercase English letters.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • maxPalindromes

      public int maxPalindromes(String s, int k)