Minimum Cost Good Caption - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3441. Minimum Cost Good Caption
Hard
50 Points
String
Dynamic Programming
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:
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:
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 "".
Examples
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:
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:
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.
3441. Minimum Cost Good Caption
Hard
50 Points
String
Dynamic Programming
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:
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:
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 "".
Examples
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:
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:
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.