Minimum Cost Good Caption

Minimum Cost Good Caption is a hard string DP problem where each final character must belong to a run of at least three equal letters. The key is to model state transitions that decide which character block ends at each index, track the minimum total edit cost, and break ties lexicographically when multiple captions share the same cost. A greedy local replacement fails because a cheap change now can force an invalid short run later.

Problem Statement

You are given a lowercase string caption and must transform it into a good caption. A good caption is one where every character belongs to a consecutive block of length at least 3, so isolated letters or pairs are not allowed anywhere in the final string.

You may change characters repeatedly, and each change contributes to the total cost. The goal is to return the good caption with the minimum possible cost, and when several good captions have the same minimum cost, return the lexicographically smallest one. If no good caption can be formed, return an empty string.

Examples

Example 1

Input: caption = "cdcd"

Output: "cccc"

It can be shown that the given caption cannot be transformed into a good caption with fewer than 2 operations. The possible good captions that can be created using exactly 2 operations are: Since "cccc" is lexicographically smaller than "dddd" , return "cccc" .

Example 2

Input: caption = "aca"

Output: "aaa"

It can be proven that the given caption requires at least 2 operations to be transformed into a good caption. The only good caption that can be obtained with exactly 2 operations is as follows: Thus, return "aaa" .

Example 3

Input: caption = "bc"

Output: ""

It can be shown that the given caption cannot be converted to a good caption by using any number of operations.

Constraints

• 1 <= caption.length <= 5 * 104
• caption consists only of lowercase English letters.

Solution Approach

Define DP by valid block endings

Use state transition dynamic programming where dp[i] represents the best way to build a valid good caption for the prefix ending before index i. From each position, try ending the next block with a chosen letter and a block length that is valid for this problem, meaning at least 3. The transition cost is the sum of edits needed to convert that substring into one repeated character. This directly matches the constraint that every final run must have size 3 or more.

Precompute conversion costs for repeated letters

For each index range and each target letter from a to z, compute the cost to convert that substring into a uniform block of that letter. With prefix sums over character frequencies or edit distances, each DP transition can evaluate a block cost quickly instead of rescanning the substring. This matters because the interview trap is trying all letters at every index without cached costs, which makes the solution too slow for length up to 5 * 10^4.

Handle tie-breaking during reconstruction

Store parent choices so you can rebuild the answer string after finding the minimum cost. When two transitions give the same cost, prefer the one that leads to the lexicographically smaller caption, not just the smaller current letter in isolation. Minimum Cost Good Caption is tricky here because a local tie can change later blocks, so tie-breaking must follow the full reconstructed suffix or an equivalent ordered state comparison.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how block costs are prepared and how many valid transitions are tested per index. With efficient preprocessing and fixed alphabet size 26, the DP can stay near linear in n up to small constant factors, while space is typically O(n) for the DP table and reconstruction data. The main trade-off is between faster transition lookup and the extra memory needed to store enough information for lexicographic tie-breaking.

What Interviewers Usually Probe

• They want dynamic programming, not greedy merging, because short runs created early can invalidate the final caption.
• They are testing whether you model the state around valid run construction instead of editing each character independently.
• They care about tie-breaking correctness, especially when multiple minimum-cost captions like cccc and dddd are both feasible.

Common Pitfalls or Variants

Common pitfalls

• Using a greedy choice on the current character and later discovering it forces a forbidden run of length 1 or 2.
• Tracking only minimum cost and forgetting that equal-cost answers must return the lexicographically smallest caption.
• Recomputing the edit cost for every substring and target letter inside the DP loops, which usually times out on long captions.

Follow-up variants

• Ask for the minimum cost only, without reconstructing the caption string.
• Change the rule so each group must have length at least k instead of exactly the threshold 3.
• Allow a different edit cost model, which changes the transition cost but keeps the same run-based DP shape.

FAQ

What is the main pattern in Minimum Cost Good Caption?

The core pattern is state transition dynamic programming over prefixes, where each transition appends a block of one repeated letter and enforces the rule that every run has length at least three.

Why does a greedy strategy fail on this problem?

A greedy change can look optimal for the current index but still leave behind a run of length 1 or 2 later. This problem couples nearby decisions through the run-length constraint, so local edits are not independent.

Why is lexicographic tie-breaking tricky here?

Two captions can have the same minimum edit cost, so you cannot stop once cost is minimized. You must compare candidate reconstructions carefully because the smaller current block choice does not always guarantee the smaller full caption.

Why can the answer be an empty string?

If the caption length is too short to form any run of at least three, no valid good caption exists. For example, a length-2 string can never satisfy the rule no matter how characters are changed.

How should I think about the example with cdcd?

The best target caption must be built from valid repeated blocks, and both cccc and dddd can be reached with the same minimum cost. Since the costs tie, the correct answer is cccc because it is lexicographically smaller.