2024-09-21: In go, given a string s, each character in the string is either a lowercase letter or a question mark '?' . For a string t containing only lowercase letters, we define cost(i) to be the number of occurrences of the same character as t[i] in the first i characters of t.
The fraction of the string t is the sum of cost(i) for all positions i.
The task now is to replace all question marks '?' with lowercase letters that minimizes the fraction of the string s. If there is more than one replacement scheme that minimizes the score, then return the one with the smallest dictionary order.
Enter: s = "????" .
Output: "abc".
Explanation: In this example, we replace the question mark '?' in s in s to get "abc".
For the string "abc" , cost(0) = 0 , cost(1) = 0 and cost(2) = 0 .
The score of "abc" is 0.
Other modifications to s to get a score of 0 are the strings "cba", "abz" and "hey".
Of these strings, we return the one with the smallest dictionary order.
The broad steps are as follows:
1. Initialize an integer array freq of size 27 for recording the number of occurrences of each character, initially all 0, with position 26 as the sentinel.
2. Iterate over the string s. If the character is not '?' , then accumulate at the corresponding position in freq.
3. Sort the freq array to get the sorted array f.
4. Count the number of question marks '?' in the string s in string s. Initialize limit and extra to 0.
5. Iterate through the array f from 1 and calculate the number of increased characters sum generated by each character value change.
6. If the number of question marks is less than or equal to sum, update limit and extra and jump out of the loop.
7. According to limit and extra update the target replacement array target, the number of occurrences does not exceed the limit of character values updated to limit, if the extra is greater than 0, the additional allocation to the character value of the smaller character.
8. Iterate over the string s and replace the question mark '? Replace the question mark '?' with the target array target, in the order of least dictionary order.
9. Return the replaced string as the final result.
Overall complexity analysis
-
Time complexity: traversing string s has O(n) time complexity, sorting time complexity is O(nlogn), and overall time complexity is O(nlogn).
-
Space complexity: in addition to the string s itself, the extra integer arrays freq and target of size 27 are used, as well as some auxiliary variables, and the total extra space complexity is small, O(1).
Answer 2024-09-21:
chatgpt
Title from leetcode3081.
The complete code for go is as follows:
package main
import (
"fmt"
"math"
"slices"
"strings"
)
func minimizeStringValue(s string) string {
freq := [27]int{26: / 26} // sentinel
for _, c := range s {
if c != '?' {
freq[c-'a']++
}
}
f := freq
(f[:])
var limit, extra int
q := (s, "?")
for i := 1; ; i++ {
sum := i * (f[i] - f[i-1])
if q <= sum {
limit, extra = f[i-1]+q/i, q%i
break
}
q -= sum
}
target := freq
for i, c := range freq[:26] {
if c > limit {
continue
}
target[i] = limit
if extra > 0 { // There is also the possibility of assigning an additional
extra--
target[i]++
}
}
ans := []byte(s)
j := byte(0)
for i, c := range ans {
if c != '?' {
continue
}
for freq[j] == target[j] {
j++
}
freq[j]++
ans[i] = 'a' + j
}
return string(ans)
}
func main() {
s := "???"
(minimizeStringValue(s))
}
