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 theminimum value , return the lexicographically smallest one.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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 <= 10^5
  • s[i] is either a lowercase English letter or '?'.

Solution

Method 1 - Greedy: Assign Unused Letters to Minimize Value

Intuition

To minimize the value, we want to avoid repeating any letter as much as possible. For each ‘?’, we should pick the smallest lexicographical letter that hasn’t appeared before in the string so far. If all 26 letters have appeared, pick ‘a’.

Approach

  1. Iterate through the string from left to right.
  2. Maintain a set of used letters so far.
  3. For each ‘?’, pick the smallest letter not in the set, or ‘a’ if all are used.
  4. For each non-’?’ character, add it to the set.
  5. Build the result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

string minimizeValue(string s) {
    unordered_set<char> used;
    string res = s;
    for (int i = 0; i < res.size(); ++i) {
        if (res[i] == '?') {
            for (char c = 'a'; c <= 'z'; ++c) {
                if (!used.count(c)) {
                    res[i] = c;
                    break;
                }
            }
            if (res[i] == '?') res[i] = 'a';
            used.insert(res[i]);
        } else {
            used.insert(res[i]);
        }
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func minimizeValue(s string) string {
    used := make(map[byte]struct{})
    res := []byte(s)
    for i := 0; i < len(res); i++ {
        if res[i] == '?' {
            found := false
            for c := byte('a'); c <= 'z'; c++ {
                if _, ok := used[c]; !ok {
                    res[i] = c
                    found = true
                    break
                }
            }
            if !found {
                res[i] = 'a'
            }
            used[res[i]] = struct{}{}
        } else {
            used[res[i]] = struct{}{}
        }
    }
    return string(res)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
public class Solution {
    public String minimizeValue(String s) {
        Set<Character> used = new HashSet<>();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '?') {
                for (char c = 'a'; c <= 'z'; c++) {
                    if (!used.contains(c)) {
                        arr[i] = c;
                        break;
                    }
                }
                if (arr[i] == '?') arr[i] = 'a';
                used.add(arr[i]);
            } else {
                used.add(arr[i]);
            }
        }
        return new String(arr);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

fun minimizeValue(s: String): String {
    val used = mutableSetOf<Char>()
    val arr = s.toCharArray()
    for (i in arr.indices) {
        if (arr[i] == '?') {
            var found = false
            for (c in 'a'..'z') {
                if (c !in used) {
                    arr[i] = c
                    found = true
                    break
                }
            }
            if (!found) arr[i] = 'a'
            used.add(arr[i])
        } else {
            used.add(arr[i])
        }
    }
    return String(arr)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def minimizeValue(s: str) -> str:
    used = set()
    res = list(s)
    for i in range(len(res)):
        if res[i] == '?':
            for c in map(chr, range(ord('a'), ord('z')+1)):
                if c not in used:
                    res[i] = c
                    break
            if res[i] == '?':
                res[i] = 'a'
            used.add(res[i])
        else:
            used.add(res[i])
    return ''.join(res)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::collections::HashSet;
fn minimize_value(s: &str) -> String {
    let mut used = HashSet::new();
    let mut res: Vec<char> = s.chars().collect();
    for i in 0..res.len() {
        if res[i] == '?' {
            let mut found = false;
            for c in 'a'..='z' {
                if !used.contains(&c) {
                    res[i] = c;
                    found = true;
                    break;
                }
            }
            if !found {
                res[i] = 'a';
            }
            used.insert(res[i]);
        } else {
            used.insert(res[i]);
        }
    }
    res.into_iter().collect()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function minimizeValue(s: string): string {
    const used = new Set<string>();
    const arr = s.split("");
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === '?') {
            let found = false;
            for (let c = 97; c <= 122; c++) {
                const ch = String.fromCharCode(c);
                if (!used.has(ch)) {
                    arr[i] = ch;
                    found = true;
                    break;
                }
            }
            if (!found) arr[i] = 'a';
            used.add(arr[i]);
        } else {
            used.add(arr[i]);
        }
    }
    return arr.join("");
}

Complexity

  • ⏰ Time complexity: O(N * 26) = O(N), where N is the length of s (since 26 is constant).
  • 🧺 Space complexity: O(26) = O(1), for the used set.