We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost Good Caption

Difficulty: Hard

Problem 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. You can perform operations to change characters to their immediate neighbors in the alphabet. Your task is to convert the given caption into a good caption using the minimum number of operations, and return the lexicographically smallest one. If it is impossible to create a good caption, return an empty string.

Key Insights

  • A good caption requires every character to appear consecutively at least 3 times.
  • Changing a character can only be done to its adjacent characters in the alphabet.
  • The solution must account for the minimum number of operations and the lexicographical order of the result.
  • The problem can be approached using a greedy method or dynamic programming to minimize operations.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a greedy approach where we iterate through the string and count the occurrences of each character. Whenever we find a character with fewer than 3 consecutive occurrences, we will convert it to the nearest character (either previous or next in the alphabet) to form groups of 3. We will maintain the lexicographical order by always choosing the smaller character when we have a choice. The algorithm will keep track of the number of operations and the resulting string to ensure it meets the criteria of a good caption.

Code Solutions

def min_cost_good_caption(caption: str) -> str:
    n = len(caption)
    if n < 3:
        return ""

    result = []
    i = 0

    while i < n:
        count = 1
        while i + 1 < n and caption[i] == caption[i + 1]:
            count += 1
            i += 1
        
        # If we have fewer than 3, we need to change some characters
        if count < 3:
            if i == 0:
                return ""  # Impossible to fix
            # Change to the previous character
            previous_char = chr(ord(caption[i]) - 1) if caption[i] > 'a' else None
            # Change to the next character
            next_char = chr(ord(caption[i]) + 1) if caption[i] < 'z' else None
            
            # Choose the best character to fill in
            if previous_char and (next_char is None or previous_char < next_char):
                result.append(previous_char * 3)
            else:
                result.append(next_char * 3)
        else:
            result.append(caption[i] * count)
        
        i += 1

    # Join the result and ensure all characters are in groups of at least 3
    final_result = ''.join(result)
    if len(final_result) < n:
        return ""
    
    return final_result
← Back to All Questions