Show problems as
Classic problem #2472HardTwo PointersStringDynamic ProgrammingGreedy

Maximum Number of Non-overlapping Palindrome Substrings

Real-world version: Cutting Mirror Pieces From the Ribbon
Tracked in this browser only
Read Maximum Number of Non-overlapping Palindrome Substrings on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ribbon ribbon holds lowercase letters. A piece is a stretch of neighbouring letters that reads the same forwards and backwards and is at least k letters long.

Cut out as many pieces as possible so that no two of them share a letter of the ribbon.

Return the largest number of pieces that can be cut.

Examples

Example 1

Input
ribbon = "aaaa", k = 2
Output
2

Cut the first two letters and then the last two. Three pieces of two letters could never fit inside four letters.

Example 2

Input
ribbon = "aba", k = 2
Output
1

No two neighbouring letters match, so the only stretch reading the same both ways and long enough is the whole ribbon.

Example 3

Input
ribbon = "ab", k = 2
Output
0

The two letters differ, so the ribbon holds no two-letter stretch reading the same both ways.

Constraints

  • 1 <= k <= ribbon.length <= 2000
  • ribbon holds only lowercase English letters

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_palindromes(ribbon: str, k: int) -> int:
Java
public int maxPalindromes(String ribbon, int k)

More on the same topics