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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Replace Question Marks in String to Minimize Its Value

Number: 3354

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a string s in which each character is either a lowercase English letter or a question mark '?', replace all the question marks with lowercase English letters such that the overall "value" of the string is minimized. The value is defined as follows: for each character in the string t (after replacement), cost(i) is the number of previous occurrences of t[i] (i.e. appearing in the range [0, i-1]) and the value is the sum of cost(i) for all indices. In addition, if there are multiple ways to minimize the value, the lexicographically smallest resulting string should be returned.

Key Insights

  • The cost at each position is increased when a letter that already appeared is used again.
  • To minimize the cost, it is optimal to avoid repeating letters as much as possible.
  • For each '?' encountered, choose a letter that has not been used before (count equals 0) if possible, yielding an immediate cost of 0.
  • If every letter has been used before (i.e. no letter with count 0), choose the letter with the smallest current count to minimize the additional cost.
  • In case of ties, choose the lexicographically smallest letter.
  • Process the string from left-to-right while maintaining counts for each letter.

Space and Time Complexity

Time Complexity: O(n * 26) = O(n), where n is the length of the string, since for each character we scan a constant 26 letters. Space Complexity: O(1) extra space, aside from the output string (only a fixed-size array of 26 counts is used).

Solution

The solution processes the string from left-to-right. A counts array for the 26 lowercase letters is maintained.

  • For each character in s:
    • If the character is not '?', append it to the result and update the count.
    • If the character is '?', iterate over the alphabet:
      • First, check for a letter with count equal to 0. If found, select the lexicographically smallest such letter.
      • If every letter has already appeared (none with count 0), choose the letter with the smallest count (using lexicographical order as a tie-breaker).
    • Append the chosen letter to the result and update counts accordingly.

This greedy approach ensures that each replacement at a '?' minimizes the incremental cost and overall additional sum, while also ensuring the final string is lexicographically smallest among those with minimal cost.

Code Solutions

def minimize_string_value(s: str) -> str:
    # Initialize counts for each lowercase letter ('a' to 'z')
    counts = [0] * 26
    result = []
    for char in s:
        if char != '?':
            # Append fixed character to the result and update its count
            result.append(char)
            counts[ord(char) - 97] += 1
        else:
            # For a '?' choose the lexicographically smallest letter with count 0 if possible
            candidate = None
            for i in range(26):
                if counts[i] == 0:
                    candidate = i
                    break
            # If all letters have been used, choose the one with the minimal count
            if candidate is None:
                candidate = min(range(26), key=lambda i: counts[i])
            # Append the selected letter and update its count
            letter = chr(candidate + 97)
            result.append(letter)
            counts[candidate] += 1
    return ''.join(result)

# Example usage:
print(minimize_string_value("a?a?"))  # Expected output: "abac"
← Back to All Questions