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, 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 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"Replacing the question marks with "abc" gives value 0, and among all strings with value 0 it is the lexicographically smallest.
Example 2
Input
s = "a?a?"Output
"abac"Replacing the question marks with "b" and "c" makes "abac", whose value is 1.
Constraints
- 1 <= s.length <= 10^5
- s[i] is either a lowercase English letter or '?'.