Replace Question Marks in String to Minimize Its Value

Problem Description

You are given a string s. s[i] is either a lowercase English letter or '?'. Your task is to replace all occurrences of '?' in s with any lowercase English letter so that the value of s is minimized. The value of s is defined as the sum of costs for all indices, where cost(i) is the number of characters equal to s[i] that appeared before it. Return a string denoting the modified string with replaced occurrences of '?'. If there are multiple strings resulting in the minimum value, return the lexicographically smallest one.

Key Insights

• The '?' characters can be replaced with lowercase letters to minimize the total cost.
• The cost for a character is determined by how many times it has appeared before its position in the string.
• To achieve the minimum value, we need to ensure that the same character does not appear consecutively as much as possible.
• When replacing '?', we should aim to use the smallest available character that hasn't been used recently to maintain the lexicographical order.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, as we perform a single pass through the string. Space Complexity: O(1), since we only use a fixed amount of additional space for character counts.

Solution

The problem can be solved using a greedy approach where we iterate through the string and replace '?' with the smallest possible character that does not increase the cost. We maintain a count of occurrences of each character seen so far to efficiently compute the costs.

1. Initialize an array to count occurrences of each character.
2. Iterate through the string:
   • If the character is '?', replace it with the smallest character (a, b, c) that can minimize the cost based on previously seen characters.
   • Update the count for the chosen character.
3. Construct the final string with the replacements.

Code Solutions