Replace wildcards in a binary string avoiding three identical consecutive letters-CodePudding

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?

My solution:


        #include <bits/stdc  .h>
        using namespace std;
    
        bool isValid(string &s, int pos)
        {
            if (pos < 2)
                return true;
            for (int i = 1; i < pos; i  )
            {
                if (s[i - 1] == s[i] && s[i] == s[i   1])
                {
                    return false;
                }
            }
            return true;
        }
    
        void solve(string &s, int pos, string &ans)
        {
    
            if (pos == s.length())
            {
                ans = s;
                return;
            }
            if (!isValid(s, pos))
                return;
            if (s[pos] == '?')
            {
                s[pos] = 'a';
                if (isValid(s, pos))
                    solve(s, pos   1, ans);
                s[pos] = 'b';
                if (isValid(s, pos))
                {
                    solve(s, pos   1, ans);
                }
                s[pos] = '?';
            }
            else
                solve(s, pos   1, ans);
        }
    
        int main()
        {
            string s;
            cin >> s;
            string ans;
            solve(s, 0, ans);
            cout << ans;
            return 0;
        }

CodePudding user response：

first of all x??y with more than 1? would always pass

a??b => abab (produce no increase of length on both side, *no impact* at following)
a??a => abba (no impact)
a???????????????????b => ab?????????????????ab

so you only need to consider the case with single ?

aa? => aab (no other possibility)
a?a => aba (no impact)

so the only problem comes to a?b

aa?b => aabb (as describe in aa?)
ba?b => baab (no impact)
^a?b => ^aab (only for start, no impact)

You did at most 2 look-back and 2 look-ahead so this is a O(n) solution,

If it can contain invalid input, simply run another O(n) check

CodePudding user response：

The O(n) dynamic program has four states: a character is either a_first, a_second, b_first or b_second. Let dp[i] represent the possibility of creating a valid string up to index i. Then:

dp[i][a_first] = True
dp[i][a_second] = True
dp[i][b_first] = True
dp[i][b_second] = True
  where i < 0

if s[i] == '?':
  dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]
  dp[i][a_second] = dp[i-1][a_first]
  dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]
  dp[i][b_second] = dp[i-1][b_first]
  
else if s[i] == 'a':
  dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]
  dp[i][a_second] = dp[i-1][a_first]
  dp[i][b_first] = False
  dp[i][b_second] = False
  
else:
  dp[i][a_first] = False
  dp[i][a_second] = False
  dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]
  dp[i][b_second] = dp[i-1][b_first]

where i ≥ 0

To get the strings, we can follow the paths backwards that maintain True throughout and keep the consecutive character constraint.

Python code:

def f(s):
  dp = [[None] * 4 for _ in range(len(s))]

  def get_dp(i, j):
    return True if i < 0 else dp[i][j]

  for i in range(len(s)):
    if s[i] == '?':
      dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)
      dp[i][1] = get_dp(i-1, 0) 
      dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)
      dp[i][3] = get_dp(i-1, 2)
  
    elif s[i] == 'a':
      dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)
      dp[i][1] = get_dp(i-1, 0)
      dp[i][2] = False
      dp[i][3] = False
  
    else:
      dp[i][0] = False
      dp[i][1] = False
      dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)
      dp[i][3] = get_dp(i-1, 2)

  # Build the output
  result = []

  i = len(s) - 1
  need = None

  while i >= 0:
    if dp[i][0] and need != 'b':
      result.append('a')
      need = None if (len(result) == 1 or result[-2] == 'b') else 'b'
      i-= 1
    elif dp[i][1] and need != 'b':
      result.extend(['a', 'a'])
      need = 'b'
      i -= 2
    elif dp[i][2] and need != 'a':
      result.append('b')
      need = None if (len(result) == 1 or result[-2] == 'a') else 'a'
      i -= 1
    elif dp[i][3] and need != 'a':
      result.extend(['b', 'b'])
      need = 'a'
      i -= 2
    else:
      return ""

  return "".join(reversed(result))

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?",
  "????",
  "??",
  "?????",
  "??????"
]

for s in strs:
  print("%s\n%s\n" % (s, f(s)))

"""
a?bb
aabb

??abb
baabb

a?b?aa
aabbaa

?bb?
abba

aa?bb


aa??aa
aabbaa

ab???bb?
abbaabba

????
abaa

??
aa

?????
aabaa

??????
baabaa
"""

CodePudding user response：

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

CodePudding user response：

You can try the algorithm below. Let's start changing sequences of ? into a or b from left to right.

For a single ?

a?a -> aba
a?b -> try aab, then (in case of aa?b) try abb
b?a -> try bba, then (in case of bb?a) try baa
b?b -> bab

For a long (more then one ?) sequence start adding alternating a and b from both ends:

a?????????b -> ab???????ab -> aba?????bab -> abab???abab -> ababa?babab -> ababaababab

We can have 4 possible pattern all being valid

a?????????a -> ababa .... ababa, so we'll have either abababa or ababbaba   
a?????????b -> ababa .... babab, so we'll have either abababab or ababbabab  
b?????????a -> babab .... ababa, so we'll have either babababa or babaababa
b?????????b -> babab .... babab, so we'll have either bababab or babaabab

CodePudding user response：

Implementing @appleapple's O(N) solution in JavaScript (but should be relatively simple to port to C ):

let solve = (str) => {
  let opposite = {"a":"b","b":"a"};
  let curr_idx = 0;
  let output = [];
  
  let lookahead  = (x) => ((curr_idx x<0)||(curr_idx x>=str.length)?null:str[curr_idx   x]);
  let lookbehind = (x) => (curr_idx-x<0?null:output[curr_idx - x])
  let matches    = (x,y) => (x == y || x == null || y == null);
  let is_replacement = (x) => (x == '?');
  
  while ( curr_idx < str.length )
  {
    let curr = lookbehind(1) || 'b';
    let i = 0;
    let next = lookahead(i);
    while (is_replacement(next))
    {
        i;
      next = lookahead(i);
    }
    
    if (next == null)
    {
      for (; i > 0; --i)
      {
        curr = opposite[curr];
        output.push( curr );
      }
      break;
    }

    if (i > 1)
    {
      let j = 0;
      for (; j < i/ 2;   j)
      {
        curr = opposite[curr];
        output.push( curr );
      }
      for (; j < i;   j)
      {
        output.push( (j%2) == (i%2) ? next : opposite[next] );
      }
    }
    else if (i == 1)
    {
      if (curr == lookbehind(2) || matches(curr, next))
      {
        output.push( opposite[curr] );
      }
      else
      {
        output.push( curr );
      }
    }

    if ( next != null )
    {
      output.push( next );
    }
    curr_idx  = i   1;
  }
  
  return output.join("");
};

let tests = [
  "?",
  "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",
  "??abb",
  "a?b?aa",
  "ab???bb?",
];

for ( let test of tests )
{
  console.log( `${test} -> ${solve(test)}` );
}

CodePudding user response：

I quickly tried out the solution I proposed in the comments:

#include <iostream>
#include <string>

int main(void)
{
    std::string s = "?????aaa??bbaa????";
    std::cout << s <<'\n';
    for(char &c:s)
        if(c=='?')
            c='a';
    
    std::cout << s <<'\n';

    for(int i =0; i<s.size()-2; i  )
    {
        if(s[i] == 'a' 
        && s[i 1] == 'a' 
        && s[i 2] == 'a' )
        {
            s[i 1] = 'b';
            i  ;
        }
    }
    std::cout << s <<'\n';
    return 0;
}

It seems to be conformant with the given rules. but maybe there's some case to check and fix.