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.
You can perform the following operation any number of times:
- Choose an index
i, where0 <= i < n, and change the character at that index to the character immediately before it in the alphabet, ifcaption[i] != 'a'. - Choose an index
i, where0 <= i < n, and change the character at that index to the character immediately after it in the alphabet, ifcaption[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"Both
"cccc" and "dddd" can be created using exactly 2 operations, and "cccc" is lexicographically smaller.Example 2
Input
caption = "aca"Output
"aaa"The caption requires at least 2 operations, and the only good caption obtainable with exactly 2 operations is
"aaa".Constraints
- 1 <= caption.length <= 5 * 10^4
- caption consists only of lowercase English letters.