替换二进制字符串中的通配符，避免出现三个相同的连续字母

Question

给定长度为N的字符串S，返回一个字符串，该字符串是将'?'字符串S中的每个字符替换为一个'a'或一个'b'字符的结果，并且不包含三个相同的连续字母（换句话说，处理后的字符串中'aaa'不可能'bbb'出现这两个字母）。

例子：

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

我使用回溯解决了这个问题，但是我的解决方案很慢并且不适用于更大的 N 值，有更好的方法吗？

Answer 1

首先x??y有超过1个？总会过去

• a??b => abab（两侧长度不会增加，*后续不会产生影响*）
• a??a => abba（没有影响）
• a???????????????????b => ab?????????????????ab

所以你只需要考虑单个的情况?

• aa? => aab（没有其他可能）
• a?a => aba（没有影响）

所以唯一的问题是a?b

• aa?b => aabb（如中所述aa?）
• ba?b => baab（没有影响）
• ^a?b=> ^aab（仅用于启动，无影响）

你最多做了 2 次回顾和 2 次展望，所以这是一个O(n)解决方案，

如果它可能包含无效输入，只需运行另一次O(n)检查

_{我在另一个答案中添加了可能的实现）}

Answer 2

（另请参阅我的贪婪O(n) 时间、O(1) 空间解决方案，其中包括随机测试，与 MTO 的代码进行比较。）

\n

动态程序O(n)有四种状态：字符为a_first、a_second或b_first。b_second让dp[i]我们表示创建有效字符串到索引的可能性i。然后：

\n

dp[i][a_first] = True\ndp[i][a_second] = True\ndp[i][b_first] = True\ndp[i][b_second] = True\n  where i < 0\n\nif s[i] == \'?\':\n  dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]\n  dp[i][a_second] = dp[i-1][a_first]\n  dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]\n  dp[i][b_second] = dp[i-1][b_first]\n  \nelse if s[i] == \'a\':\n  dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]\n  dp[i][a_second] = dp[i-1][a_first]\n  dp[i][b_first] = False\n  dp[i][b_second] = False\n  \nelse:\n  dp[i][a_first] = False\n  dp[i][a_second] = False\n  dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]\n  dp[i][b_second] = dp[i-1][b_first]\n\nwhere i \xe2\x89\xa5 0\n

\n

为了获取字符串，我们可以沿着始终保持 True 的向后路径并保持连续字符约束。

\n

Python代码：

\n

dp[i][a_first] = True\ndp[i][a_second] = True\ndp[i][b_first] = True\ndp[i][b_second] = True\n  where i < 0\n\nif s[i] == \'?\':\n  dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]\n  dp[i][a_second] = dp[i-1][a_first]\n  dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]\n  dp[i][b_second] = dp[i-1][b_first]\n  \nelse if s[i] == \'a\':\n  dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]\n  dp[i][a_second] = dp[i-1][a_first]\n  dp[i][b_first] = False\n  dp[i][b_second] = False\n  \nelse:\n  dp[i][a_first] = False\n  dp[i][a_second] = False\n  dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]\n  dp[i][b_second] = dp[i-1][b_first]\n\nwhere i \xe2\x89\xa5 0\n

\n

输出：

\n

def f(s):\n  dp = [[None] * 4 for _ in range(len(s))]\n\n  def get_dp(i, j):\n    return True if i < 0 else dp[i][j]\n\n  for i in range(len(s)):\n    if s[i] == \'?\':\n      dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)\n      dp[i][1] = get_dp(i-1, 0) \n      dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)\n      dp[i][3] = get_dp(i-1, 2)\n  \n    elif s[i] == \'a\':\n      dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)\n      dp[i][1] = get_dp(i-1, 0)\n      dp[i][2] = False\n      dp[i][3] = False\n  \n    else:\n      dp[i][0] = False\n      dp[i][1] = False\n      dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)\n      dp[i][3] = get_dp(i-1, 2)\n\n  # Build the output\n  result = []\n\n  i = len(s) - 1\n  need = None\n\n  while i >= 0:\n    if dp[i][0] and need != \'b\':\n      result.append(\'a\')\n      need = None if (len(result) == 1 or result[-2] == \'b\') else \'b\'\n      i-= 1\n    elif dp[i][1] and need != \'b\':\n      result.extend([\'a\', \'a\'])\n      need = \'b\'\n      i -= 2\n    elif dp[i][2] and need != \'a\':\n      result.append(\'b\')\n      need = None if (len(result) == 1 or result[-2] == \'a\') else \'a\'\n      i -= 1\n    elif dp[i][3] and need != \'a\':\n      result.extend([\'b\', \'b\'])\n      need = \'a\'\n      i -= 2\n    else:\n      return ""\n\n  return "".join(reversed(result))\n

\n

Answer 3

我的答案中规则的可能实施。

这个实现是

• 左到右
• 具有 2 次后视和 1 次前视的单遍（尽管进行了初始检查）
• O(n)时间复杂度
• 可以是O(1)空间复杂度，因为上下文最多 4 个字符
• 不检查无效输入

首先合并规则

• 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否则（也暗示a??）
  • aa? => aab
  • a?a => aba
  • aa?b => aabb

然后设置边界条件。

该规则需要字符串不以 s 开头?（如果只是将它们填充到另一遍中则不需要）

• ^?? => a?（就好像我们在前面加上一个b）
• ^?a => ba

该规则需要 2 次回顾，所以a?b我只是预先应用它以防止在主循环内进行检查

• 预填充^a?b => ^aab

代码（WandBox 链接）

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