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

1/**
2 * [3081] Replace Question Marks in String to Minimize Its Value
3 *
4 * You are given a string s. s[i] is either a lowercase English letter or '?'.
5 * 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].
6 * The value of t is the sum of cost(i) for all indices i.
7 * For example, for the string t = "aab":
8 * 
9 * 	cost(0) = 0
10 * 	cost(1) = 1
11 * 	cost(2) = 0
12 * 	Hence, the value of "aab" is 0 + 1 + 0 = 1.
13 * 
14 * Your task is to replace all occurrences of '?' in s with any lowercase English letter so that the value of s is minimized.
15 * Return a string denoting the modified string with replaced occurrences of '?'. If there are multiple strings resulting in the minimum value, return the <span data-keyword="lexicographically-smaller-string">lexicographically smallest</span> one.
16 *  
17 * <strong class="example">Example 1:
18 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
19 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> s = "???" </span>
20 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> "abc" </span>
21 * Explanation:  In this example, we can replace the occurrences of '?' to make s equal to "abc".
22 * For "abc", cost(0) = 0, cost(1) = 0, and cost(2) = 0.
23 * The value of "abc" is 0.
24 * Some other modifications of s that have a value of 0 are "cba", "abz", and, "hey".
25 * Among all of them, we choose the lexicographically smallest.
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
29 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">s = "a?a?"</span>
30 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">"abac"</span>
31 * Explanation:  In this example, the occurrences of '?' can be replaced to make s equal to "abac".
32 * For "abac", cost(0) = 0, cost(1) = 0, cost(2) = 1, and cost(3) = 0.
33 * The value of "abac" is 1.
34 * </div>
35 *  
36 * Constraints:
37 * 
38 * 	1 <= s.length <= 10^5
39 * 	s[i] is either a lowercase English letter or '?'.
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/replace-question-marks-in-string-to-minimize-its-value/
45// discuss: https://leetcode.com/problems/replace-question-marks-in-string-to-minimize-its-value/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn minimize_string_value(s: String) -> String {
51        String::new()
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3081() {
63    }
64}
65