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?

Answer

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

The Code (WandBox link)

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[0]='a'; // ?? => a? // not really necessary if use another pass to fill prefix '?'s
   if(s.starts_with("?a")  || s.starts_with("?b"))  s[0]=inverse(s[1]); // ?a => ba // not really necessary as above
   if(s.starts_with("a??") || s.starts_with("b??")) s[1]=inverse(s[0]); // not really necessary, just to prevent access s[-1]
   if(s.starts_with("a?b") || s.starts_with("b?a")) s[1]=s[0]; // ^a?b => aab
   
   /// primary loop
   
   for(auto curr=s.data(); curr!=s.data()+s.size(); ++curr)
   if(*curr=='?'){
      if(curr[-1]!=curr[1] && curr[-2]==curr[1]) *curr=curr[-1]; // ba?b => baab
      else *curr = inverse(curr[-1]); // a? => b (rule coaslesing)
   }
    
   return s;
}