1class Solution {
2    public String minimizeStringValue(String s) {
3        // Initialize a count array for the alphabet letters
4        int[] letterCount = new int[26];
5        int n = s.length(); // Length of the input string
6        int questionMarkCount = 0; // Counts the number of '?' characters
7        char[] chars = s.toCharArray(); // Convert the input string to a character array
8
9        // Count occurrences of each letter and number of '?'
10        for (char c : chars) {
11            if (c == '?') {
12                ++questionMarkCount;
13            } else {
14                ++letterCount[c - 'a'];
15            }
16        }
17
18        // Use a priority queue to keep track of the letters with the smallest counts
19        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> 
20            a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
21
22        // Add the count of each letter into the priority queue
23        for (int i = 0; i < 26; ++i) {
24            priorityQueue.offer(new int[] {letterCount[i], i});
25        }
26
27        // Array to store the index of letters that will replace '?'
28        int[] replacementIndices = new int[questionMarkCount];
29        for (int j = 0; j < questionMarkCount; ++j) {
30            int[] current = priorityQueue.poll(); // Get the letter with the smallest count
31            replacementIndices[j] = current[1]; // Store its index
32            priorityQueue.offer(new int[] {current[0] + 1, current[1]}); // Add back with incremented count
33        }
34
35        // Sort the replacement indices to minimize lexicographic order
36        Arrays.sort(replacementIndices);
37
38        // Replace '?' with the corresponding minimal letters
39        for (int i = 0, j = 0; i < n; ++i) {
40            if (chars[i] == '?') {
41                chars[i] = (char) (replacementIndices[j++] + 'a'); // Replace '?' with the replacement letter
42            }
43        }
44
45        // Return the modified string
46        return new String(chars);
47    }
48}
49

1#include <string>
2#include <queue>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7public:
8    string minimizeStringValue(std::string s) {
9        int count[26] = {}; // Array to keep track of character frequencies, initialized to 0
10        int questionMarkCount = 0; // To count occurrences of '?'
11      
12        // Iterate through each character in the string
13        for (char& c : s) {
14            if (c == '?') {
15                ++questionMarkCount; // Increment count of '?' characters
16            } else {
17                ++count[c - 'a']; // Increment frequency of the character
18            }
19        }
20      
21        // Priority queue (min-heap) to store frequency and character index
22        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
23        for (int i = 0; i < 26; ++i) {
24            pq.push({count[i], i}); // Push pair of frequency and character index onto the queue
25        }
26      
27        std::vector<int> temp(questionMarkCount); // Vector to store indices of the least frequent characters to replace '?'
28      
29        // Distribute '?' over the characters to balance the frequency
30        for (int i = 0; i < questionMarkCount; ++i) {
31            auto [frequency, charIndex] = pq.top();
32            pq.pop();
33            temp[i] = charIndex; // Store the character index
34            pq.push({frequency + 1, charIndex}); // Increment frequency and reinsert into the queue
35        }
36      
37        // Sort the vector to ensure lexicographical order
38        std::sort(temp.begin(), temp.end());
39        int tempIndex = 0;
40      
41        // Replace '?' with the least frequent character
42        for (char& c : s) {
43            if (c == '?') {
44                c = temp[tempIndex++] + 'a'; // Convert index back to character
45            }
46        }
47      
48        return s; // Return the minimized string
49    }
50};
51

1function minimizeStringValue(s: string): string {
2    let count: number[] = Array(26).fill(0); // Array to keep track of character frequencies, initialized to 0
3    let questionMarkCount: number = 0; // To count occurrences of '?'
4  
5    // Iterate through each character in the string
6    for (let c of s) {
7        if (c === '?') {
8            questionMarkCount++; // Increment count of '?' characters
9        } else {
10            count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++; // Increment frequency of the character
11        }
12    }
13  
14    // Priority queue (min-heap) to store frequency and character index
15    // Using a min-heap by sorting array with pop/push operations
16    let pq: [number, number][] = []; 
17    for (let i = 0; i < 26; i++) {
18        pq.push([count[i], i]); // Push pair of frequency and character index onto the array
19    }
20  
21    // Sort the array to act as a priority queue
22    pq.sort((a, b) => a[0] - b[0]);
23  
24    let temp: number[] = Array(questionMarkCount); // Array to store indices of the least frequent characters to replace '?'
25  
26    // Distribute '?' over the characters to balance the frequency
27    for (let i = 0; i < questionMarkCount; i++) {
28        let [frequency, charIndex] = pq.shift()!; // Get the least frequent character
29        temp[i] = charIndex; // Store the character index
30        pq.push([frequency + 1, charIndex]); // Increment frequency and reinsert into the queue
31        pq.sort((a, b) => a[0] - b[0]); // Re-sort the array
32    }
33  
34    // Replace '?' with the least frequent character
35    let tempIndex: number = 0;
36    let result: string[] = s.split(''); // Convert string to an array of characters for modification
37
38    for (let i = 0; i < result.length; i++) {
39        if (result[i] === '?') {
40            result[i] = String.fromCharCode(temp[tempIndex++] + 'a'.charCodeAt(0)); // Convert index back to character
41        }
42    }
43  
44    return result.join(''); // Convert the array back to a string and return it
45}
46