Replace Question Marks in String to Minimize Its Value

Replace Question Marks in String to Minimize Its Value - Problem

Hash Table String Greedy Sorting Heap (Priority Queue) Counting Medium

You are given a string s. Each character 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 (no 'a' before index 0)
cost(1) = 1 (one 'a' before index 1)
cost(2) = 0 (no 'b' before index 2)

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

Input & Output

Example 1 — Basic Case

$ Input: s = "?ab?"

› Output: "aaba"

💡 Note: Replace first '?' with 'a' (min freq), second '?' with 'a' (still min among remaining). Result has value: cost(0)=0 + cost(1)=1 + cost(2)=0 + cost(3)=2 = 3

Example 2 — All Question Marks

$ Input: s = "???"

› Output: "abc"

💡 Note: Greedily pick 'a', then 'b', then 'c' to minimize value. Each character appears for first time so total value = 0

Example 3 — Mixed Pattern

$ Input: s = "a?a?"

› Output: "abac"

💡 Note: First '?' becomes 'b' (min freq), second '?' becomes 'c' (min freq). Value = 0+0+1+0 = 1

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either a lowercase English letter or '?'

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with '?' characters to replace

Cost Calculation

Each character's cost = count of same chars before it

Greedy Strategy

Replace each '?' with minimum frequency letter

Key Takeaway

🎯 Key Insight: Greedy approach works because choosing the least frequent letter at each step minimizes the total cost function

Asked in

G Google 35 M Microsoft 28 a Amazon 22 M Meta 18

The key insight is to greedily replace each '?' with the letter having minimum frequency so far. This minimizes the cost function since each character's cost equals the count of same characters before it. Best approach is greedy frequency counting with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue (Min-Heap)	O(n log 26)	O(1)	Use a min-heap to efficiently track and select the letter with minimum frequency
Greedy with Frequency Counting	O(n)	O(1)	For each '?', greedily choose the letter with minimum frequency so far
Brute Force with Backtracking	O(26^k × n²)	O(n)	Try all possible combinations of letters for each '?' and pick the minimum value result

Priority Queue (Min-Heap) — Algorithm Steps

Initialize min-heap with all 26 letters at frequency 0
Process each character left to right
For fixed letters: find in heap, increment frequency, re-heapify
For '?': extract min, use that letter, increment and push back

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize heap

All 26 letters start with frequency 0

Extract minimum

For each '?', take top of heap (min frequency)

Update and re-heapify

Increment frequency and maintain heap property

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int freq;
    char letter;
} LetterFreq;

typedef struct {
    LetterFreq* arr;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap() {
    MinHeap* heap = malloc(sizeof(MinHeap));
    heap->capacity = 26;
    heap->size = 0;
    heap->arr = malloc(heap->capacity * sizeof(LetterFreq));
    
    // Initialize with all 26 letters
    for (int i = 0; i < 26; i++) {
        heap->arr[i] = (LetterFreq){0, 'a' + i};
        heap->size++;
    }
    
    // Build heap
    for (int i = heap->size / 2 - 1; i >= 0; i--) {
        // Heapify down from i
        int curr = i;
        while (1) {
            int smallest = curr;
            int left = 2 * curr + 1;
            int right = 2 * curr + 2;
            
            if (left < heap->size && 
                (heap->arr[left].freq < heap->arr[smallest].freq ||
                 (heap->arr[left].freq == heap->arr[smallest].freq && heap->arr[left].letter < heap->arr[smallest].letter))) {
                smallest = left;
            }
            
            if (right < heap->size && 
                (heap->arr[right].freq < heap->arr[smallest].freq ||
                 (heap->arr[right].freq == heap->arr[smallest].freq && heap->arr[right].letter < heap->arr[smallest].letter))) {
                smallest = right;
            }
            
            if (smallest != curr) {
                LetterFreq temp = heap->arr[curr];
                heap->arr[curr] = heap->arr[smallest];
                heap->arr[smallest] = temp;
                curr = smallest;
            } else {
                break;
            }
        }
    }
    
    return heap;
}

LetterFreq extractMin(MinHeap* heap) {
    LetterFreq min = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    
    // Heapify down
    int curr = 0;
    while (1) {
        int smallest = curr;
        int left = 2 * curr + 1;
        int right = 2 * curr + 2;
        
        if (left < heap->size && 
            (heap->arr[left].freq < heap->arr[smallest].freq ||
             (heap->arr[left].freq == heap->arr[smallest].freq && heap->arr[left].letter < heap->arr[smallest].letter))) {
            smallest = left;
        }
        
        if (right < heap->size && 
            (heap->arr[right].freq < heap->arr[smallest].freq ||
             (heap->arr[right].freq == heap->arr[smallest].freq && heap->arr[right].letter < heap->arr[smallest].letter))) {
            smallest = right;
        }
        
        if (smallest != curr) {
            LetterFreq temp = heap->arr[curr];
            heap->arr[curr] = heap->arr[smallest];
            heap->arr[smallest] = temp;
            curr = smallest;
        } else {
            break;
        }
    }
    
    return min;
}

void insert(MinHeap* heap, LetterFreq item) {
    heap->arr[heap->size] = item;
    int curr = heap->size;
    heap->size++;
    
    // Heapify up
    while (curr > 0) {
        int parent = (curr - 1) / 2;
        if (heap->arr[curr].freq < heap->arr[parent].freq ||
            (heap->arr[curr].freq == heap->arr[parent].freq && heap->arr[curr].letter < heap->arr[parent].letter)) {
            LetterFreq temp = heap->arr[curr];
            heap->arr[curr] = heap->arr[parent];
            heap->arr[parent] = temp;
            curr = parent;
        } else {
            break;
        }
    }
}

char* solution(char* s) {
    int len = strlen(s);
    char* result = malloc((len + 1) * sizeof(char));
    strcpy(result, s);
    
    MinHeap* heap = createHeap();
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '?') {
            LetterFreq min = extractMin(heap);
            result[i] = min.letter;
            insert(heap, (LetterFreq){min.freq + 1, min.letter});
        } else {
            // Update frequency of existing letter
            LetterFreq temp[26];
            int tempSize = 0;
            
            while (heap->size > 0) {
                LetterFreq lf = extractMin(heap);
                if (lf.letter == s[i]) {
                    temp[tempSize++] = (LetterFreq){lf.freq + 1, lf.letter};
                } else {
                    temp[tempSize++] = lf;
                }
            }
            
            for (int j = 0; j < tempSize; j++) {
                insert(heap, temp[j]);
            }
        }
    }
    
    free(heap->arr);
    free(heap);
    result[len] = '\0';
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log 26)

For each character, heap operations take O(log 26) which is effectively O(1)

⚡ Linearithmic

Space Complexity

O(1)

Heap stores exactly 26 elements regardless of input size

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Priority Queue (Min-Heap) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler