3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution

In this guide, you will get 3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution with the best time and space complexity. The solution to Replace Question Marks in String to Minimize Its Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Replace Question Marks in String to Minimize Its Value solution in C++
  4. Replace Question Marks in String to Minimize Its Value solution in Java
  5. Replace Question Marks in String to Minimize Its Value solution in Python
  6. Additional Resources
3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution image

Problem Statement of Replace Question Marks in String to Minimize Its Value

You are given a string s. s[i] is either a lowercase English letter or ‘?’.
For a string t having length m containing only lowercase English letters, we define the function cost(i) for an index i as the number of characters equal to t[i] that appeared before it, i.e. in the range [0, i – 1].
The value of t is the sum of cost(i) for all indices i.
For example, for the string t = “aab”:

cost(0) = 0
cost(1) = 1
cost(2) = 0
Hence, the value of “aab” is 0 + 1 + 0 = 1.

Your task is to replace all occurrences of ‘?’ in s with any lowercase English letter so that the value of s is minimized.
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.

See also  2815. Max Pair Sum in an Array LeetCode Solution

Example 1:

Input: s = “???”
Output: “abc”
Explanation: In this example, we can replace the occurrences of ‘?’ to make s equal to “abc”.
For “abc”, cost(0) = 0, cost(1) = 0, and cost(2) = 0.
The value of “abc” is 0.
Some other modifications of s that have a value of 0 are “cba”, “abz”, and, “hey”.
Among all of them, we choose the lexicographically smallest.

Example 2:

Input: s = “a?a?”
Output: “abac”
Explanation: In this example, the occurrences of ‘?’ can be replaced to make s equal to “abac”.
For “abac”, cost(0) = 0, cost(1) = 0, cost(2) = 1, and cost(3) = 0.
The value of “abac” is 1.

Constraints:

1 <= s.length <= 105
s[i] is either a lowercase English letter or '?'.

Complexity Analysis

  • Time Complexity: O(\texttt{sort})
  • Space Complexity: O(n)

3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution in C++

class Solution {
 public:
  string minimizeStringValue(string s) {
    string ans;
    vector<int> count(26);
    vector<char> letters;

    for (const char c : s)
      if (c != '?')
        ++count[c - 'a'];

    for (const char c : s) {
      if (c != '?')
        continue;
      const char minFreqLetter = getMinFreqLetter(count);
      letters.push_back(minFreqLetter);
      ++count[minFreqLetter - 'a'];
    }

    ranges::sort(letters);
    int i = 0;  // letters' index

    for (const char c : s)
      ans += c == '?' ? letters[i++] : c;

    return ans;
  }

 private:
  char getMinFreqLetter(const vector<int>& count) {
    char minFreqLetter = 'a';
    for (char c = 'b'; c <= 'z'; ++c)
      if (count[c - 'a'] < count[minFreqLetter - 'a'])
        minFreqLetter = c;
    return minFreqLetter;
  }
};
/* code provided by PROGIEZ */

3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution in Java

class Solution {
  public String minimizeStringValue(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];
    List<Character> letters = new ArrayList<>();

    for (final char c : s.toCharArray())
      if (c != '?')
        ++count[c - 'a'];

    for (final char c : s.toCharArray()) {
      if (c != '?')
        continue;
      final char minFreqLetter = getMinFreqLetter(count);
      letters.add(minFreqLetter);
      ++count[minFreqLetter - 'a'];
    }

    Collections.sort(letters);
    int i = 0; // letters' index

    for (final char c : s.toCharArray())
      sb.append(c == '?' ? letters.get(i++) : c);

    return sb.toString();
  }

  private char getMinFreqLetter(int[] count) {
    char minFreqLetter = 'a';
    for (char c = 'b'; c <= 'z'; ++c)
      if (count[c - 'a'] < count[minFreqLetter - 'a'])
        minFreqLetter = c;
    return minFreqLetter;
  }
}
// code provided by PROGIEZ

3081. Replace Question Marks in String to Minimize Its Value LeetCode Solution in Python

class Solution:
  def minimizeStringValue(self, s: str) -> str:
    ans = []
    count = collections.Counter(s)
    letters = []

    del count['?']

    def getMinFreqLetter(count: dict[str, int]) -> str:
      minFreqLetter = 'a'
      for c in string.ascii_lowercase:
        if count[c] < count[minFreqLetter]:
          minFreqLetter = c
      return minFreqLetter

    for c in s:
      if c == '?':
        minFreqLetter = getMinFreqLetter(count)
        letters.append(minFreqLetter)
        count[minFreqLetter] += 1

    letters.sort()
    i = 0  # letters' index

    for c in s:
      if c == '?':
        ans.append(letters[i])
        i += 1
      else:
        ans.append(c)

    return ''.join(ans)
# code by PROGIEZ

Additional Resources

See also  1688. Count of Matches in Tournament LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.