Replace wildcards in a binary string avoiding three identical consecutive letters

Question

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 1

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;
}

Answer 2

The greedy version below seems to work. This way, we could have constant space aside from one output string. Can someone help find a counter example? I wrote this idea before implementing the straightforward dynamic program (see this revision). Try to maintain sequences of two of the same character as much as possible.

The last section of the code below includes random testing with this and MTO's code.

Python code:

def is_valid(s):
  if not s:
    return True
  char = "x"
  count = 0
  for c in s:
    if c != char:
      char, count = c, 1
    else:
      count += 1
      if count == 3:
        return False
  return True


# My greedy solution
def f(s):
  if len(s) == 2:
    return s.replace('?', 'a')
    
  aa = ['a', 'a']
  bb = ['b', 'b']

  out = []
  i = 0
  a, b = 0, 0

  while i < len(s):
    if s[i] == 'a' or (s[i] == '?' and b == 2):
      if s[i] == 'a' and a == 2:
        if s[i-3:i-1] == "??":
          out[i-3], out[i-2] = out[i-2], out[i-3]
          a -= 1
        else:
          return ""
      out.append('a')
      a, b = a + 1, 0
      i += 1
    elif s[i] == 'b' or (s[i] == '?' and a == 2):
      if s[i] == 'b' and b == 2:
        if s[i-3:i-1] == "??":
          out[i-3], out[i-2] = out[i-2], out[i-3]
          b -= 1
        else:
          return ""
      out.append('b')
      a, b = 0, b + 1
      i += 1
    elif i == len(s) - 1:
      out.append('a' if b else 'b')
      i += 1
    elif i == len(s) - 2:
      if s[i+1] == '?':
        out.extend(aa if b else bb)
      else:
        out.append('a' if b else 'b')
        out.append(s[i+1])
      i += 2
    elif s[i+1] == '?':
      if a:
        out.append('a')
        a, b = a + 1, 0
      else:
        out.append('b')
        a, b = 0, b + 1
      i += 1
    elif s[i+1] == 'a':
      if a or b < 2:
        out.append('b')
        a, b = 0, b + 1
      else:
        out.append('a')
        a, b = a + 1, 0
      i += 1
    elif s[i+1] == 'b':
      if b or a < 2:
        out.append('a')
        a, b = a + 1, 0
      else:
        out.append('b')
        a, b = 0, b + 1
      i += 1

  return ''.join(out)


# https://stackoverflow.com/a/69322213/2034787
# Code by MTO
def solve(_str):
  opposite = {"a": "b", "b": "a"}
  curr_idx = 0
  output = []
  
  lookahead  = lambda x: None if ((curr_idx + x < 0) or (curr_idx + x >= len(_str))) else _str[curr_idx + x]
  lookbehind = lambda x: None if curr_idx-x< 0 else output[curr_idx - x]
  matches = lambda x, y: x == y or x == None or y == None
  is_replacement = lambda x: x == '?'
  
  while curr_idx < len(_str):
    curr = lookbehind(1) or 'b'
    i = 0
    next = lookahead(i)
    while is_replacement(next):
      i += 1
      next = lookahead(i)
    
    if next == None:
      # Found the end of the string.
      # Append characters opposite to the previous for each ?
      for _ in range(i, 0, -1):
        curr = opposite[curr]
        output.append( curr )
      break

    if (i > 1):
      # Found multiple successive ?s
      # Handle the first half of the ?s by
      # Append alternating characters from the previous character.
      j = 0
      while j < i / 2:
        curr = opposite[curr]
        output.append( curr )
        j += 1
      # Then handle the second half of the ?s
      # append alternating characters to the next character after the ?s.
      while j < i:
        output.append( next if (j%2) == (i%2) else opposite[next] )
        j += 1
  
    elif i == 1:
      # Found a single ?
      prev = lookbehind(2)
      if curr == prev and curr == opposite[next] and next == lookahead(2):
        # No solution.
        return None

      if curr == prev or matches(curr, next):
        output.append( opposite[curr] )
      else:
        output.append( curr )

    if next != None:
      # Output the next non-? character.
      output.append( next )

    curr_idx += i + 1
  
  return ''.join(output)


strs = [
  "a?bb", # "aabb"
  "??abb", # "ababb" or "bbabb" or "baabb"
  "a?b?aa", # "aabbaa"
  "?bb?",
  "aa?bb", # NO SOLUTION
  "aa??aa", # "aabbaa"
  "ab???bb?",
  "????",
  "??",
  "?????",
  "??????",
  "?",
  "a?",
  "a??",
  "a???",
  "b?",
  "b??",
  "b???",
  "a?a",
  "a?b",
  "b?a",
  "b?b",
  "a??a",
  "a??b",
  "b??a",
  "b??b",
  "aa?",
  "ba?",
  "a?bb",
  "?bb?",
  "??abb",
  "a?b?aa",
  "ab???bb?",
  "aa?bb"
]


for s in strs:
  _solve = solve(s)
  _f = f(s)
  print("%s\n%s, %s, %s, %s\n" % (s, is_valid(_f), is_valid(_solve), _solve, _f))


import random

def get_random(n):
  char = 'x'
  count = 0
  out = []
  not_c = lambda c: 'a' if c == 'b' else 'b'

  for _ in range(n):
    c = ['a', 'b'][int(random.random() * 2)]
    if c != char:
      out.append(c)
      char, count = c, 1
    elif count == 2:
      out.append(not_c(c))
      char, count = not_c(c), 1
    else:
      out.append(c)
      count += 1

  for i in range(n):
     if int(random.random() * 2):
      out[i] = '?'

  return ''.join(out)

num_tests = 1000
n = 20

print("Starting random tests...")

for _ in range(num_tests):
  s = get_random(n)
  _solve = solve(s)
  _f = f(s)
  valid_solve = is_valid(_solve)
  valid_f = is_valid(_f)
  if not valid_f or not valid_solve:
    print(s, valid_f, valid_solve, _f, _solve)
    break

print("Done testing")

Answer 3

An iterative backtracking solution.

• isValid only checks whether inserting a char c at position pos would create an issue, without iterating over the whole string;

• maintain a variable int dir = +-1 to know whether we're moving forward or backwards in the string (this is only important so that we know in which direction to move when skipping over a non-? character in the original string);

• forest of if/else if/else to decide where we're at (non-? to skip, or fresh ? going forward, or already tried a, or already tried both a and b);

• solve has a boolean return value which is true if a solution was found (pos == s.length()), or false if no solution was found (pos == (unsigned int) -1).

#include <iostream>
#include <vector>

bool isValid(char c, std::string const &s, unsigned int pos)
{
    return ((pos < 2 || s[pos - 2] != c || s[pos - 1] != c)
         && (pos < 1 || pos + 1 >= s.length() || s[pos - 1] != c || s[pos + 1] != c)
         && (pos + 2 >= s.length() || s[pos + 1] != c || s[pos + 2] != c));
}
bool solve(std::string const &in, std::string &out)
{
    unsigned int pos = 0;
    int dir = 1;
    out = in;
    while (pos < in.size())
    {
        if (in[pos] != '?')  // nothing to do: keep moving (forward or backward)
        {
            pos += dir;
        }
        else if (out[pos] == '?')  // going forward, will try 'a' then 'b'
        {
            dir = 1;
            if (isValid('a', out, pos))
            {
                out[pos] = 'a';
                pos += dir;
            }
            else if (isValid('b', out, pos))
            {
                out[pos] = 'b';
                pos += dir;
            }
            else
            {
                dir = -1;
                pos += dir;
            }
        }
        else if (out[pos] == 'a' && isValid('b', out, pos)) // going backward, already tried 'a'
        {
            out[pos] = 'b';
            dir = 1;
            pos += dir;
        }
        else // already tried everything: backtrack
        {
            dir = -1;
            out[pos] = '?';
            pos += dir;
        }
    }
    return (pos == in.size());
}

int main(void)
{
  std::vector<std::string> ins  = {"a?bb", "??abb", "a?b?aa", "aa?bb"};
  std::vector<std::string> outs = {"", "", "", "", ""};
  for (unsigned int i = 0; i < ins.size(); ++i)
  {
      if (solve(ins[i], outs[i]))
          std::cout << ins[i] << "  -->  " << outs[i] << std::endl;
      else
          std::cout << ins[i] << "  -->  NO SOLUTION" << std::endl;
  }
  return 0;
}

Output:

a?bb  -->  aabb
??abb  -->  ababb
a?b?aa  -->  aabbaa
aa?bb  -->  NO SOLUTION