3441. Minimum Cost Good Caption LeetCode Solution
In this guide, you will get 3441. Minimum Cost Good Caption LeetCode Solution with the best time and space complexity. The solution to Minimum Cost Good Caption problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Cost Good Caption solution in C++
- Minimum Cost Good Caption solution in Java
- Minimum Cost Good Caption solution in Python
- Additional Resources
Problem Statement of Minimum Cost Good Caption
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:
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:
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:
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 * 104
caption consists only of lowercase English letters.
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
3441. Minimum Cost Good Caption LeetCode Solution in C++
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);
}
};
/* code provided by PROGIEZ */3441. Minimum Cost Good Caption LeetCode Solution in Java
class Solution {
public String minCostGoodCaption(String caption) {
final int n = caption.length();
if (n < 3)
return "";
final int kMaxCost = 1_000_000_000;
int[][][] dp = new int[n][26][3];
Arrays.stream(dp).forEach(A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, kMaxCost)));
// 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 = kMaxCost;
for (int i = n - 2; i >= 0; --i) {
int newMinCost = kMaxCost;
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 = 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, (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);
}
}
// code provided by PROGIEZ3441. Minimum Cost Good Caption LeetCode Solution in Python
class Solution:
def minCostGoodCaption(self, caption: str) -> str:
n = len(caption)
if n < 3:
return ''
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
dp = [[[kMaxCost] * 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 = kMaxCost
for i in range(n - 2, -1, -1):
newMinCost = kMaxCost
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 = kMaxCost
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))
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.