TheRealSamuel/LeetCodeProblem

1{2    "id": 3701,3    "name": "minimum_cost_good_caption",4    "difficulty": "Hard",5    "link": "https://leetcode.com/problems/minimum-cost-good-caption/",6    "date": "2025-01-18 00:00:00",7    "task_description": "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.",8    "public_test_cases": [9        {10            "label": "Example 1",11            "input": "caption = \"cdcd\"",12            "output": "\"cccc\" "13        },14        {15            "label": "Example 2",16            "input": "caption = \"aca\"",17            "output": "\"aaa\" "18        },19        {20            "label": "Example 3",21            "input": "caption = \"bc\"",22            "output": "\"\" "23        }24    ],25    "private_test_cases": [],26    "haskell_template": "minCostGoodCaption :: String -> String\nminCostGoodCaption caption ",27    "ocaml_template": "let minCostGoodCaption (caption: string) : string =  ",28    "scala_template": "def minCostGoodCaption(caption: String): String = { \n    \n}",29    "java_template": "class Solution {\n    public String minCostGoodCaption(String caption) {\n        \n    }\n}",30    "python_template": "class Solution(object):\n    def minCostGoodCaption(self, caption):\n        \"\"\"\n        :type caption: str\n        :rtype: str\n        \"\"\"\n        "31}