Skip to content

3081. Replace Question Marks in String to Minimize Its Value 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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)