Replace All ?'s to Avoid Consecutive Repeating Characters

Replace All ?'s to Avoid Consecutive Repeating Characters - Problem

String Easy

Given a string s containing only lowercase English letters and the '?' character, convert all the '?' characters into lowercase letters such that the final string does not contain any consecutive repeating characters.

You cannot modify the non '?' characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Input & Output

Example 1 — Basic Case

$ Input: s = "?zs"

› Output: "azs"

💡 Note: Replace '?' with 'a'. Since 'a' ≠ 'z', no consecutive repeating characters exist. Result: "azs"

Example 2 — Multiple Question Marks

$ Input: s = "ubv?w"

› Output: "ubvaw"

💡 Note: Replace '?' with 'a'. Check: 'v' ≠ 'a' and 'a' ≠ 'w', so no consecutive repeats. Result: "ubvaw"

Example 3 — Adjacent Conflicts

$ Input: s = "?a?"

› Output: "bac"

💡 Note: First '?' cannot be 'a' (next char), so use 'b'. Second '?' cannot be 'a' (prev char), so use 'c'. Result: "bac"

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters and '?' characters

Visualization

Tap to expand

Understanding the Visualization

Input

String with '?' characters that need replacement

Process

Replace each '?' with a letter that differs from neighbors

Output

Valid string with no consecutive repeating characters

Key Takeaway

🎯 Key Insight: With 26 letters available and at most 2 neighbors to avoid, we can always find a valid replacement in constant time

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The greedy approach is optimal: iterate through the string and replace each '?' with the first letter from 'abc' that doesn't match its neighbors. Since we have 26 letters and at most 2 neighbors to avoid, a solution always exists. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Single Pass Replacement	O(n)	O(1)	Replace each '?' with the first valid letter that doesn't conflict with neighbors
Brute Force - Try All Combinations	O(26^k)	O(k)	Generate all possible letter combinations and find one without consecutive repeats

Greedy - Single Pass Replacement — Algorithm Steps

Convert string to character array for modification
For each '?' character, try letters starting from 'a'
Check if current letter conflicts with left or right neighbor
Use first valid letter found and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Find ?

Process each '?' character from left to right

Try a,b,c

Test 'a', then 'b', then 'c' until one doesn't conflict

Assign

Use the first valid letter and move to next position

Code -

solution.c — C

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

char* solution(char* s) {
    int n = strlen(s);
    char* result = malloc((n + 1) * sizeof(char));
    strcpy(result, s);
    
    for (int i = 0; i < n; i++) {
        if (result[i] == '?') {
            // Try letters 'a', 'b', 'c'... until finding valid one
            for (char c = 'a'; c <= 'c'; c++) {
                // Check if conflicts with previous character
                if (i > 0 && result[i-1] == c) {
                    continue;
                }
                // Check if conflicts with next character
                if (i < n-1 && result[i+1] == c) {
                    continue;
                }
                // Found valid character
                result[i] = c;
                break;
            }
        }
    }
    
    return result;
}

int main() {
    char s[100001];
    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)

Single pass through string, constant work per '?' character (at most 3 letters to try)

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for variables, modifies input in-place

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 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

Greedy - Single Pass Replacement — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler