# Replace Question Marks in String to Minimize Its Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/replace-question-marks-in-string-to-minimize-its-value)
Canonical: https://scaleengineer.com/dsa/problems/replace-question-marks-in-string-to-minimize-its-value
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String, Heap (Priority Queue)
---
## Problem
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._

**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 `'?'`.

# Approaches
## Greedy Approach with Linear Scan
The core idea behind solving this problem is to understand how the 'value' of a string is calculated. The value is the sum of `k*(k-1)/2` for each character, where `k` is its total count. To minimize this sum, we need to keep the character counts as balanced as possible. This suggests a greedy strategy.

We have a number of '?'s to replace, say `q`. For each replacement, we should choose a character that results in the smallest possible increase in the total value. The marginal increase in value when adding an instance of a character `c` that already appears `k` times is `k`. Therefore, at each step, we should greedily choose the character with the current minimum frequency.

To handle the secondary requirement of returning the lexicographically smallest string, we apply two rules:
1.  When determining the set of `q` characters to use for replacement, if there's a tie in minimum frequency (e.g., 'b' and 'c' both appear 0 times), we choose the lexicographically smaller character ('b'). This makes the multiset of replacement characters itself lexicographically smaller.
2.  After determining this multiset, we sort these characters and place them into the '?' positions from left to right. This ensures the final string is as small as possible.

This approach implements the greedy strategy by repeatedly scanning through all 26 alphabet characters to find the one with the minimum current frequency.
**Time:** O(N + q * A + q log q), where N is the length of the string, q is the number of '?', and A is the alphabet size (26). The initial scan of the string is O(N). Determining the `q` replacement characters takes `q` iterations, with each iteration scanning `A` characters, totaling O(q * A). Sorting the replacements takes O(q log q). Building the final string takes O(N). Since A is a constant, the complexity simplifies to O(N + q log q). · **Space:** O(N + A), where N is the length of the string and A is the alphabet size (26). This is because we store the indices of '?' (up to O(N)), the replacement characters (up to O(N)), and the character counts (O(A)). If we consider the output string as part of the complexity, it's O(N). The auxiliary space is O(q + A), where q is the number of question marks.
**Pros:** The approach is relatively straightforward to understand and implement.; It correctly minimizes the string's value and produces the lexicographically smallest result among optimal solutions.
**Cons:** The process of finding the character with the minimum frequency involves a linear scan through all 26 characters for each of the `q` question marks. This is less efficient than using a data structure optimized for finding minimums, such as a priority queue.
### Explanation
```java
class Solution {
    public String minimizeStringValue(String s) {
        int[] counts = new int[26];
        List<Integer> qIndices = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '?') {
                qIndices.add(i);
            } else {
                counts[c - 'a']++;
            }
        }

        int q = qIndices.size();
        if (q == 0) {
            return s;
        }

        List<Character> replacements = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int minCount = Integer.MAX_VALUE;
            char charToUse = ' ';
            // Find char with min count, breaking ties lexicographically
            for (char c = 'a'; c <= 'z'; c++) {
                if (counts[c - 'a'] < minCount) {
                    minCount = counts[c - 'a'];
                    charToUse = c;
                }
            }
            replacements.add(charToUse);
            counts[charToUse - 'a']++;
        }

        Collections.sort(replacements);

        char[] sChars = s.toCharArray();
        for (int i = 0; i < q; i++) {
            sChars[qIndices.get(i)] = replacements.get(i);
        }

        return new String(sChars);
    }
}
```
### Algorithm
*   **Count Frequencies and '?'s:**
    1.  Create an integer array `counts` of size 26, initialized to zero, to store the frequencies of characters 'a' through 'z'.
    2.  Create a list `q_indices` to store the original indices of the '?' characters.
    3.  Iterate through the input string `s` from left to right. For each character:
        *   If it's a letter, increment the corresponding counter in the `counts` array.
        *   If it's a '?', add its index to `q_indices`.
*   **Determine Replacement Characters:**
    1.  Let `q` be the number of '?'s (the size of `q_indices`).
    2.  Create a list of characters called `replacements`.
    3.  Loop `q` times to decide which character to use for each '?':
        a.  Initialize `min_count` to a very large value and `char_to_add` to a placeholder.
        b.  Iterate through all characters from 'a' to 'z'. In this inner loop, find the character that has the minimum count in the `counts` array. If multiple characters share the same minimum count, the one that comes first alphabetically is chosen due to the loop's order.
        c.  Add the chosen character (`char_to_add`) to the `replacements` list.
        d.  Increment the count of `char_to_add` in the `counts` array to reflect its addition.
*   **Construct the Final String:**
    1.  Sort the `replacements` list in alphabetical order.
    2.  Convert the input string `s` into a character array `s_chars` for easy modification.
    3.  Iterate `q` times. In each iteration `i`, take the `i`-th index from `q_indices` and the `i`-th character from the sorted `replacements` list, and place the character at that index in `s_chars`.
    4.  Convert `s_chars` back to a string and return it.

## Optimized Greedy Approach with Priority Queue
This approach is an optimization of the previous greedy method. The fundamental logic of minimizing value by balancing character counts and ensuring lexicographical order remains the same. The key difference lies in how we efficiently find the character with the minimum frequency at each step.

Instead of a linear scan through all 26 characters for each of the `q` replacements, we use a min-priority queue. The priority queue is a data structure specifically designed to provide quick access to the minimum (or maximum) element. By storing the character frequencies in a priority queue, we can retrieve the best character to add in `O(log A)` time, where `A` is the alphabet size.

We configure the priority queue to order elements first by frequency, and then by character value for tie-breaking. This ensures we always pick the character that minimizes the value cost, and among those, the one that leads to a lexicographically smaller set of replacement characters. This makes the process of determining the `q` replacement characters significantly faster, especially when `q` is large.
**Time:** O(N + A log A + q log A + q log q). The initial scan is O(N). Building the priority queue of size A takes O(A log A). The main loop runs `q` times, with each poll/offer operation taking O(log A), for a total of O(q log A). Sorting replacements is O(q log q). As A is a small constant (26), `log A` is also a small constant. The dominant terms are O(N + q log q). · **Space:** O(N + A), where N is the string length and A is the alphabet size. The auxiliary space complexity is O(q + A) for storing `q_indices`, `replacements`, `counts`, and the priority queue.
**Pros:** Highly efficient, as it uses the optimal data structure (priority queue) for repeatedly finding the minimum element.; Provides the optimal solution in terms of both value and lexicographical order.; The time complexity is better than the linear scan approach for the character selection part.
**Cons:** The implementation is slightly more complex due to the use of a `PriorityQueue` with a custom comparator.
### Explanation
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public String minimizeStringValue(String s) {
        int[] counts = new int[26];
        List<Integer> qIndices = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '?') {
                qIndices.add(i);
            } else {
                counts[c - 'a']++;
            }
        }

        int q = qIndices.size();
        if (q == 0) {
            return s;
        }

        // PriorityQueue stores pairs of [count, character_index]
        // It's a min-heap, ordered by count, then by character_index
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        for (int i = 0; i < 26; i++) {
            pq.offer(new int[]{counts[i], i});
        }

        List<Character> replacements = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int[] top = pq.poll();
            char charToUse = (char) ('a' + top[1]);
            replacements.add(charToUse);
            top[0]++;
            pq.offer(top);
        }

        Collections.sort(replacements);

        char[] sChars = s.toCharArray();
        for (int i = 0; i < q; i++) {
            sChars[qIndices.get(i)] = replacements.get(i);
        }

        return new String(sChars);
    }
}
```
### Algorithm
*   **Count Frequencies and '?'s:**
    1.  This step is identical to the previous approach. We calculate initial character `counts` and find all `q_indices`.
*   **Setup Priority Queue:**
    1.  Create a min-priority queue. This queue will store elements representing each character and its frequency.
    2.  The elements can be pairs or a small array like `[frequency, character_index]`.
    3.  The priority queue must be configured with a custom comparator to order elements first by `frequency` (ascending), and then by `character_index` (ascending) to break ties.
    4.  Populate the priority queue by adding an entry for each of the 26 characters with its initial count from the `counts` array.
*   **Determine Replacement Characters:**
    1.  Let `q` be the number of '?'s.
    2.  Create a list of characters called `replacements`.
    3.  Loop `q` times:
        a.  Extract the element with the highest priority (lowest frequency, then lowest character value) from the priority queue. Let this be `(freq, char_idx)`.
        b.  Add the corresponding character to the `replacements` list.
        c.  Insert a new element `(freq + 1, char_idx)` back into the priority queue to update the character's frequency for subsequent steps.
*   **Construct the Final String:**
    1.  This step is also identical to the previous approach. Sort the `replacements` list and fill in the '?' positions in the original string.

# Solutions
### Java

```java
class Solution {
public
  String minimizeStringValue(String s) {
    int[] cnt = new int[26];
    int n = s.length();
    int k = 0;
    char[] cs = s.toCharArray();
    for (char c : cs) {
      if (c == '?') {
        ++k;
      } else {
        ++cnt[c - 'a'];
      }
    }
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    for (int i = 0; i < 26; ++i) {
      pq.offer(new int[]{cnt[i], i});
    }
    int[] t = new int[k];
    for (int j = 0; j < k; ++j) {
      int[] p = pq.poll();
      t[j] = p[1];
      pq.offer(new int[]{p[0] + 1, p[1]});
    }
    Arrays.sort(t);
    for (int i = 0, j = 0; i < n; ++i) {
      if (cs[i] == '?') {
        cs[i] = (char)(t[j++] + 'a');
      }
    }
    return new String(cs);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string minimizeStringValue(string s) {
    int cnt[26]{};
    int k = 0;
    for (char &c : s) {
      if (c == '?') {
        ++k;
      } else {
        ++cnt[c - 'a'];
      }
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 0; i < 26; ++i) {
      pq.push({cnt[i], i});
    }
    vector<int> t(k);
    for (int i = 0; i < k; ++i) {
      auto [v, c] = pq.top();
      pq.pop();
      t[i] = c;
      pq.push({v + 1, c});
    }
    sort(t.begin(), t.end());
    int j = 0;
    for (char &c : s) {
      if (c == '?') {
        c = t[j++] + 'a';
      }
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def minimizeStringValue(self, s: str) -> str: cnt = Counter(s) pq = [(cnt[c], c) for c in ascii_lowercase] heapify(pq) t = [] for _ in range(s . count("?")): v, c = pq[0] t . append(c) heapreplace(pq, (v + 1, c)) t . sort() cs = list(s) j = 0 for i, c in enumerate(s): if c == "?": cs[i] = t[j] j += 1 return "" . join(cs)

```