1125HardTwo PointersStringDynamic ProgrammingGreedy

Cutting Mirror Pieces From the Ribbon

Tracked in this browser only

Trains the technique from

LeetCode 2472Maximum Number of Non-overlapping Palindrome Substrings

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_palindromes(ribbon: str, k: int) -> int:

Java

public int maxPalindromes(String ribbon, int k)

The intended approach

Time O(n * k) over the ribbon.Space O(1).

Only two lengths ever need looking at. Trim a mirror piece by one letter at each end and what is left still reads the same both ways, so any piece of `k` letters or more contains, around the same middle, one of exactly `k` or `k + 1` letters. That inner piece starts later and ends sooner, so swapping the long piece for it never costs a cut and often leaves room for more. With the candidates narrowed to those two lengths, this becomes the familiar business of picking as many non-overlapping stretches as possible, which is settled by always taking the one that finishes soonest. So walk the possible right ends from the front, and at each one check whether a stretch of `k` or of `k + 1` letters ending there reads the same both ways and begins after the last cut. If it does, cut it and move the boundary to that right end. Checking the shorter length first matters only in that it begins later and so is likelier to clear the boundary. Each right end costs a mirror check of fixed length, so the whole walk is the ribbon times `k`.

Pythonentry point: max_palindromes

def max_palindromes(ribbon, k):
    n = len(ribbon)

    def mirrored(lo, hi):
        while lo < hi:
            if ribbon[lo] != ribbon[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    cuts = 0
    edge = -1
    for hi in range(n):
        for span in (k, k + 1):
            lo = hi - span + 1
            if lo >= 0 and lo > edge and mirrored(lo, hi):
                cuts += 1
                edge = hi
                break
    return cuts

The obvious version

Work along the ribbon keeping, for each cut-off point, the most pieces that can be taken from everything before it. At each point either take nothing new, or take any long-enough stretch ending there that reads the same both ways and add one to the best from before that stretch began. Every stretch is tested outright by reversing it, which costs the ribbon length cubed.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_palindromes(ribbon, k):
    n = len(ribbon)
    best = [0] * (n + 1)
    for end in range(1, n + 1):
        best[end] = best[end - 1]
        for start in range(0, end - k + 1):
            piece = ribbon[start:end]
            if piece == piece[::-1]:
                take = best[start] + 1
                if take > best[end]:
                    best[end] = take
    return best[n]

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in