Replace question marks in string to minimize its value

Hash Table String Greedy Sorting Heap (Priority Queue) Counting

29.0% acceptance

Feb 25, 2026

204

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. 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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_string_value(s: String) -> String {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let mut freq = [0i32; 26];
    for b in s.bytes() {
      if b != b'?' { freq[(b - b'a') as usize] += 1; }
    }
    let q_count = s.bytes().filter(|&b| b == b'?').count();
    // Greedily assign each '?' the letter with smallest frequency
    let mut heap: BinaryHeap<Reverse<(i32, u8)>> = (0..26u8).map(|c| Reverse((freq[c as usize], c))).collect();
    let mut assignments = vec![];
    for _ in 0..q_count {
      if let Some(Reverse((f, c))) = heap.pop() {
        assignments.push(c + b'a');
        heap.push(Reverse((f + 1, c)));
      }
    }
    assignments.sort();
    let mut ai = 0;
    s.bytes().map(|b| {
      if b == b'?' {
        let c = assignments[ai];
        ai += 1;
        c as char
      } else { b as char }
    }).collect()
  }
}