Minimum Cost Good Caption - Solution & Explanation

Problem Overview: You are given a caption string and a cost model for modifying characters. The goal is to transform the caption into a good caption while minimizing the total modification cost. The constraint that defines a good caption applies to consecutive characters, so every position you choose affects the validity of the following positions.

Approach 1: Brute Force Enumeration (Exponential Time, Exponential Space)

Generate all possible captions by replacing each character with any of the 26 lowercase letters. For every generated string, check whether it satisfies the good caption constraint and compute the total cost of modifications. Keep the minimum cost across all valid candidates. This approach explores 26^n possibilities and becomes infeasible even for moderate n. It is mainly useful to understand the structure of the problem before introducing optimization.

Approach 2: Dynamic Programming on Character States (O(n · 26 · 2) time, O(26 · 2) space)

The key observation is that the validity of the caption depends only on the most recent characters. Instead of generating full strings, track states that represent the last chosen character and how many times it has appeared consecutively. For each index i, iterate through all candidate letters a–z. Transition from previous states while enforcing the constraint on consecutive characters. The cost of choosing a letter is the modification cost between the original character and the chosen one. This forms a classic dynamic programming transition where each step depends only on the previous index.

The DP state can be defined as dp[i][c][k], meaning the minimum cost to build a valid caption up to index i, ending with character c repeated k consecutive times. When the next character is different, the consecutive counter resets. When it is the same, ensure the constraint is not violated before extending the run. Because only the previous position matters, you can compress the DP to two layers and reduce memory usage.

This approach relies heavily on efficient iteration over characters and careful state transitions. It’s a standard pattern in string problems where local constraints propagate through the sequence. The optimization works because the number of states remains small (26 letters and a small consecutive count).

Recommended for interviews: The dynamic programming state-transition approach is what interviewers expect. Starting with brute force shows you understand the search space, but recognizing that only the previous character state matters demonstrates strong DP intuition and the ability to reduce exponential problems to linear scans.