# Replace wildcards in a binary string avoiding three identical consecutive letters

Given a string S of length N, return a string that is the result of replacing each `'?'` in the string S with an `'a'` or a `'b'` character and does not contain three identical consecutive letters (in other words, neither `'aaa'` not `'bbb'` may occur in the processed string).

Examples:

```Given S="a?bb", output= "aabb"

Given S="??abb", output= "ababb" or "bbabb" or "baabb"

Given S="a?b?aa", output= "aabbaa"
```

1<=n<= 500000

I solved the problem using backtracking, but my solution is slow and won’t work for greater N values, is there a better approach?

Possible Implementation for rules in my answer.

This implementation is

• left-to-right
• single pass with 2 look-behind and 1 look-ahead (despite initial checking)
• `O(n)` time complexity
• can be `O(1)` space complexity since the context is at most 4 character
• does not check for invalid Input

First merge the rules

• `a?? => ab?`
• `a??b => abab` (`a??b => ab?b => abab`)
• `a??a => abba`
• `a???????????????????b => ab??????????????????b`
• `ba?b => baab`
• `^a?b => ^aab`
• `a? => ab` otherwise (also imply `a??`)
• `aa? => aab`
• `a?a => aba`
• `aa?b => aabb`

Then setup the boundary conditions.

The rule need the string not start with `?`s (not necessary if simply fill them in another pass)

• `^?? => a?` (as if we prepend a `b`)
• `^?a => ba`

The rule need 2 look back in case of `a?b` so I simply pre-apply it to prevent the check inside primary loop

• prefill `^a?b => ^aab`

```char inverse(char c){return c=='a'?'b':'a';}

std::string solve(std::string s){

/// boundary conditions

if(s.size()<3){
for(auto& c:s) if(c=='?') c='b';
return s;
}

if(s.starts_with("??")) s='a'; // ?? => a? // not really necessary if use another pass to fill prefix '?'s
if(s.starts_with("?a")  || s.starts_with("?b"))  s=inverse(s); // ?a => ba // not really necessary as above
if(s.starts_with("a??") || s.starts_with("b??")) s=inverse(s); // not really necessary, just to prevent access s[-1]
if(s.starts_with("a?b") || s.starts_with("b?a")) s=s; // ^a?b => aab

/// primary loop

for(auto curr=s.data(); curr!=s.data()+s.size(); ++curr)
if(*curr=='?'){
if(curr[-1]!=curr && curr[-2]==curr) *curr=curr[-1]; // ba?b => baab
else *curr = inverse(curr[-1]); // a? => b (rule coaslesing)
}

return s;
}
```