Problem

You are given a string caption of length n. A good caption is a string where every character appears in groups of at least 3 consecutive occurrences.

For example:

  • "aaabbb" and "aaaaccc" are good captions.
  • "aabbb" and "ccccd" are not good captions.

You can perform the following operation any number of times:

Choose an index i (where 0 <= i < n) and change the character at that index to either:

  • The character immediately before it in the alphabet (if caption[i] != 'a').
  • The character immediately after it in the alphabet (if caption[i] != 'z').

Your task is to convert the given caption into a good caption using the minimum number of operations, and return it. If there are multiple possible good captions, return the lexicographically smallest one among them. If it is impossible to create a good caption, return an empty string "".

Example 1

1
2
3
4
5
6
7
8
9

Input: caption = "cdcd"
Output: "cccc"
Explanation:
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:
* `"dddd"`: Change `caption[0]` and `caption[2]` to their next character `'d'`.
* `"cccc"`: Change `caption[1]` and `caption[3]` to their previous character `'c'`.
Since `"cccc"` is lexicographically smaller than `"dddd"`, return `"cccc"`.

Example 2

1
2
3
4
5
6
7
8
9

Input: caption = "aca"
Output: "aaa"
Explanation:
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:
* Operation 1: Change `caption[1]` to `'b'`. `caption = "aba"`.
* Operation 2: Change `caption[1]` to `'a'`. `caption = "aaa"`.
Thus, return `"aaa"`.

Example 3

1
2
3
4
5

Input: caption = "bc"
Output: ""
Explanation:
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 * 10^4
  • caption consists only of lowercase English letters.

Examples

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

To form a good caption, every character must appear in groups of at least 3 consecutive occurrences. We can use dynamic programming to try all possible groupings and character changes, keeping track of the minimum cost and lexicographically smallest result.

Approach

  1. Use DP: dp[i][c][cnt] is the minimum cost to build the first i characters, ending with character c and a group of size cnt (cnt = 1, 2, or >=3).
  2. For each position, try changing the character to any possible letter and extend or start a group.
  3. Only allow groups to end if their size is at least 3.
  4. Track the minimum cost and reconstruct the lexicographically smallest caption.
  5. If impossible, return an empty string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    string minimumCostGoodCaption(string caption) {
        int n = caption.size();
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(26, vector<int>(4, INT_MAX)));
        vector<vector<vector<string>>> res(n + 1, vector<vector<string>>(26, vector<string>(4, "")));
        for (int c = 0; c < 26; ++c) {
            dp[0][c][0] = 0;
        }
        for (int i = 0; i < n; ++i) {
            for (int c = 0; c < 26; ++c) {
                for (int cnt = 0; cnt < 4; ++cnt) {
                    if (dp[i][c][cnt] == INT_MAX) continue;
                    for (int nc = 0; nc < 26; ++nc) {
                        int cost = dp[i][c][cnt] + (caption[i] - 'a' != nc);
                        string next = res[i][c][cnt] + (char)('a' + nc);
                        int ncnt = (nc == c) ? min(cnt + 1, 3) : 1;
                        if (cnt >= 3 || i == 0 || nc == c) {
                            if (cost < dp[i + 1][nc][ncnt] || (cost == dp[i + 1][nc][ncnt] && next < res[i + 1][nc][ncnt])) {
                                dp[i + 1][nc][ncnt] = cost;
                                res[i + 1][nc][ncnt] = next;
                            }
                        }
                    }
                }
            }
        }
        int minCost = INT_MAX;
        string ans = "";
        for (int c = 0; c < 26; ++c) {
            if (dp[n][c][3] < minCost || (dp[n][c][3] == minCost && res[n][c][3] < ans)) {
                minCost = dp[n][c][3];
                ans = res[n][c][3];
            }
        }
        return minCost == INT_MAX ? "" : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public String minimumCostGoodCaption(String caption) {
        int n = caption.length();
        int[][][] dp = new int[n + 1][26][4];
        String[][][] res = new String[n + 1][26][4];
        for (int i = 0; i <= n; i++)
            for (int c = 0; c < 26; c++)
                Arrays.fill(dp[i][c], Integer.MAX_VALUE);
        for (int c = 0; c < 26; c++) dp[0][c][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < 26; c++) {
                for (int cnt = 0; cnt < 4; cnt++) {
                    if (dp[i][c][cnt] == Integer.MAX_VALUE) continue;
                    for (int nc = 0; nc < 26; nc++) {
                        int cost = dp[i][c][cnt] + (caption.charAt(i) - 'a' != nc ? 1 : 0);
                        String next = (res[i][c][cnt] == null ? "" : res[i][c][cnt]) + (char)('a' + nc);
                        int ncnt = (nc == c) ? Math.min(cnt + 1, 3) : 1;
                        if (cnt >= 3 || i == 0 || nc == c) {
                            if (cost < dp[i + 1][nc][ncnt] || (cost == dp[i + 1][nc][ncnt] && (res[i + 1][nc][ncnt] == null || next.compareTo(res[i + 1][nc][ncnt]) < 0))) {
                                dp[i + 1][nc][ncnt] = cost;
                                res[i + 1][nc][ncnt] = next;
                            }
                        }
                    }
                }
            }
        }
        int minCost = Integer.MAX_VALUE;
        String ans = "";
        for (int c = 0; c < 26; c++) {
            if (dp[n][c][3] < minCost || (dp[n][c][3] == minCost && (ans.equals("") || res[n][c][3].compareTo(ans) < 0))) {
                minCost = dp[n][c][3];
                ans = res[n][c][3];
            }
        }
        return minCost == Integer.MAX_VALUE ? "" : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def minimum_cost_good_caption(caption: str) -> str:
    n = len(caption)
    dp = [[[float('inf')] * 4 for _ in range(26)] for _ in range(n + 1)]
    res = [[[''] * 4 for _ in range(26)] for _ in range(n + 1)]
    for c in range(26):
        dp[0][c][0] = 0
    for i in range(n):
        for c in range(26):
            for cnt in range(4):
                if dp[i][c][cnt] == float('inf'):
                    continue
                for nc in range(26):
                    cost = dp[i][c][cnt] + (caption[i] != chr(ord('a') + nc))
                    next_str = res[i][c][cnt] + chr(ord('a') + nc)
                    ncnt = cnt + 1 if nc == c else 1
                    ncnt = min(ncnt, 3)
                    if cnt >= 3 or i == 0 or nc == c:
                        if cost < dp[i + 1][nc][ncnt] or (cost == dp[i + 1][nc][ncnt] and next_str < res[i + 1][nc][ncnt]):
                            dp[i + 1][nc][ncnt] = cost
                            res[i + 1][nc][ncnt] = next_str
    min_cost = float('inf')
    ans = ''
    for c in range(26):
        if dp[n][c][3] < min_cost or (dp[n][c][3] == min_cost and res[n][c][3] < ans):
            min_cost = dp[n][c][3]
            ans = res[n][c][3]
    return '' if min_cost == float('inf') else ans
1

// Skipped for brevity due to high memory usage in Go for this DP.
1

// Skipped for brevity due to high memory usage in Rust for this DP.

1

// Skipped for brevity due to high memory usage in TypeScript for this DP.

Complexity

  • ⏰ Time complexity: O(n * 26 * 4 * 26), as we try all possible character transitions for each position and group size.
  • 🧺 Space complexity: O(n * 26 * 4), for DP and result reconstruction tables.