Skip to content

3441. Minimum Cost Good Caption 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
 public:
  string minCostGoodCaption(string caption) {
    const int n = caption.length();
    if (n < 3)
      return "";

    constexpr int kMaxCost = 1'000'000'000;
    // dp[i][j][k] := the minimum cost of caption[i..n - 1], where j is the last
    // letter used, and k is the count of consecutive letters
    vector<vector<vector<int>>> dp(
        n, vector<vector<int>>(26, vector<int>(3, kMaxCost)));

    for (char c = 'a'; c <= 'z'; ++c)
      dp[n - 1][c - 'a'][0] = abs(caption[n - 1] - c);

    int minCost = kMaxCost;
    for (int i = n - 2; i >= 0; --i) {
      int newMinCost = kMaxCost;
      for (char c = 'a'; c <= 'z'; ++c) {
        const int j = c - 'a';
        const int changeCost = abs(caption[i] - c);
        dp[i][j][0] = changeCost + minCost;
        dp[i][j][1] = changeCost + dp[i + 1][j][0];
        dp[i][j][2] = changeCost + min(dp[i + 1][j][1], dp[i + 1][j][2]);
        newMinCost = min(newMinCost, dp[i][j][2]);
      }
      minCost = newMinCost;
    }

    // Reconstruct the string.
    string ans;
    int cost = kMaxCost;
    int letter = -1;

    // Find the initial best letter.
    for (int c = 25; c >= 0; --c)
      if (dp[0][c][2] <= cost) {
        letter = c;
        cost = dp[0][c][2];
      }

    // Add the initial triplet.
    cost -= appendLetter(caption, 0, 'a' + letter, ans);
    cost -= appendLetter(caption, 1, 'a' + letter, ans);
    cost -= appendLetter(caption, 2, 'a' + letter, ans);

    // Build the rest of the string.
    for (int i = 3; i < n;) {
      // Check if we should switch to a new letter.
      const int nextLetter = getNextLetter(dp, i, cost);
      if (nextLetter < letter || ranges::min(dp[i][letter]) > cost) {
        letter = nextLetter;
        cost -= appendLetter(caption, i, 'a' + letter, ans);
        cost -= appendLetter(caption, i + 1, 'a' + letter, ans);
        cost -= appendLetter(caption, i + 2, 'a' + letter, ans);
        i += 3;
      } else {
        cost -= appendLetter(caption, i, 'a' + letter, ans);
        i += 1;
      }
    }

    return ans;
  }

 private:
  int getNextLetter(const vector<vector<vector<int>>>& dp, int i, int cost) {
    int nextLetter = 26;  // invalid letter as the sentinel
    for (int c = 25; c >= 0; --c)
      if (cost == dp[i][c][2])
        nextLetter = c;
    return nextLetter;
  }

  int appendLetter(const string& caption, int i, char letter, string& ans) {
    ans += letter;
    return abs(caption[i] - letter);
  }
};

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
  public String minCostGoodCaption(String caption) {
    final int n = caption.length();
    if (n < 3)
      return "";

    final int MAX_COST = 1_000_000_000;
    int[][][] dp = new int[n][26][3];
    Arrays.stream(dp).forEach(A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, MAX_COST)));
    // dp[i][j][k] := the minimum cost of caption[i..n - 1], where j is the last
    // letter used, and k is the count of consecutive letters
    for (char c = 'a'; c <= 'z'; ++c)
      dp[n - 1][c - 'a'][0] = Math.abs(caption.charAt(n - 1) - c);

    int minCost = MAX_COST;
    for (int i = n - 2; i >= 0; --i) {
      int newMinCost = MAX_COST;
      for (char c = 'a'; c <= 'z'; ++c) {
        final int j = c - 'a';
        final int changeCost = Math.abs(caption.charAt(i) - c);
        dp[i][j][0] = changeCost + minCost;
        dp[i][j][1] = changeCost + dp[i + 1][j][0];
        dp[i][j][2] = changeCost + Math.min(dp[i + 1][j][1], dp[i + 1][j][2]);
        newMinCost = Math.min(newMinCost, dp[i][j][2]);
      }
      minCost = newMinCost;
    }

    // Reconstruct the string.
    StringBuilder sb = new StringBuilder();
    int cost = MAX_COST;
    int letter = -1;

    // Find the initial best letter.
    for (int c = 25; c >= 0; --c)
      if (dp[0][c][2] <= cost) {
        letter = c;
        cost = dp[0][c][2];
      }

    // Add the initial triplet.
    cost -= appendLetter(caption, 0, (char) ('a' + letter), sb);
    cost -= appendLetter(caption, 1, (char) ('a' + letter), sb);
    cost -= appendLetter(caption, 2, (char) ('a' + letter), sb);

    // Build the rest of the string.
    for (int i = 3; i < n;) {
      // Check if we should switch to a new letter.
      final int nextLetter = getNextLetter(dp, i, cost);
      if (nextLetter < letter || Arrays.stream(dp[i][letter]).min().getAsInt() > cost) {
        letter = nextLetter;
        cost -= appendLetter(caption, i, (char) ('a' + letter), sb);
        cost -= appendLetter(caption, i + 1, (char) ('a' + letter), sb);
        cost -= appendLetter(caption, i + 2, (char) ('a' + letter), sb);
        i += 3;
      } else {
        cost -= appendLetter(caption, i, (char) ('a' + letter), sb);
        i += 1;
      }
    }

    return sb.toString();
  }

  private int getNextLetter(int[][][] dp, int i, int cost) {
    int nextLetter = 26;
    for (int c = 25; c >= 0; --c)
      if (cost == dp[i][c][2])
        nextLetter = c;
    return nextLetter;
  }

  private int appendLetter(String caption, int i, char letter, StringBuilder sb) {
    sb.append(letter);
    return Math.abs(caption.charAt(i) - letter);
  }
}

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution:

  def minCostGoodCaption(self, caption: str) -> str:
    n = len(caption)
    if n < 3:
      return ''

    MAX_COST = 1_000_000_000
    # dp[i][j][k] := the minimum cost of caption[i..n - 1], where j is the last
    # letter used, and k is the count of consecutive letters
    dp = [[[MAX_COST] * 3 for _ in range(26)] for _ in range(n)]

    for c in range(26):
      dp[-1][c][0] = abs(string.ascii_lowercase.index(caption[-1]) - c)

    minCost = MAX_COST

    for i in range(n - 2, -1, -1):
      newMinCost = MAX_COST
      for c in range(26):
        changeCost = abs(string.ascii_lowercase.index(caption[i]) - c)
        dp[i][c][0] = changeCost + minCost
        dp[i][c][1] = changeCost + dp[i + 1][c][0]
        dp[i][c][2] = changeCost + min(dp[i + 1][c][1], dp[i + 1][c][2])
        newMinCost = min(newMinCost, dp[i][c][2])
      minCost = newMinCost

    # Reconstruct the string.
    ans = []
    cost = MAX_COST
    letter = -1

    # Find the initial best letter.
    for c in range(25, -1, -1):
      if dp[0][c][2] <= cost:
        letter = c
        cost = dp[0][c][2]

    # Add the initial triplet.
    cost -= self._appendLetter(caption, 0, chr(ord('a') + letter), ans)
    cost -= self._appendLetter(caption, 1, chr(ord('a') + letter), ans)
    cost -= self._appendLetter(caption, 2, chr(ord('a') + letter), ans)

    # Build the rest of the string.
    i = 3
    while i < n:
      nextLetter = self._getNextLetter(dp, i, cost)
      if nextLetter < letter or min(dp[i][letter]) > cost:
        letter = nextLetter
        cost -= self._appendLetter(caption, i, chr(ord('a') + letter), ans)
        cost -= self._appendLetter(caption, i + 1, chr(ord('a') + letter), ans)
        cost -= self._appendLetter(caption, i + 2, chr(ord('a') + letter), ans)
        i += 3
      else:
        cost -= self._appendLetter(caption, i, chr(ord('a') + letter), ans)
        i += 1

    return ''.join(ans)

  def _getNextLetter(self, dp: list[list[list[int]]], i: int, cost: int) -> int:
    nextLetter = 26
    for c in range(25, -1, -1):
      if cost == dp[i][c][2]:
        nextLetter = c
    return nextLetter

  def _appendLetter(
      self,
      caption: str,
      i: int,
      letter: str,
      ans: list[str]
  ) -> int:
    ans.append(letter)
    return abs(ord(caption[i]) - ord(letter))