替换字符串通配符避免三个连续相同字符的高效算法咨询

回溯法本质是暴力枚举所有问号的替换可能，时间复杂度为指数级O(2^k)（k为问号数量），当n达到5e5量级时完全不可能运行完成。本题可以用O(n)时间复杂度的贪心算法求解，完全满足性能要求。

核心逻辑 #

由于可选字符只有a和b两种，我们只需要保证替换后的任意位置字符，不与前两位字符同时相同，即可避免出现aaa或bbb的违规子串。具体实现步骤如下：

1. 将输入字符串转为可变的字符列表（字符串为不可变类型，转列表修改效率更高）
2. 处理边界特殊情况：
   • 如果全字符串都是问号，直接按aab循环填充即可，比如长度为5就填充aabaa，天然避免三个连续相同字符
   • 处理开头的连续问号：找到第一个非问号的位置，从该位置倒序往前填充，每个问号都填与后一位不同的字符
   • 处理结尾的连续问号：找到最后一个非问号的位置，从该位置正序往后填充，每个问号都填与前一位不同的字符
3. 处理中间的问号：从左到右遍历字符列表，遇到问号时：
   • 优先尝试填a，检查是否和前两位字符同时相同，若不会产生违规则填a
   • 若填a会违规，则直接填b即可

示例验证 #

以输入"??abb"为例：

• 第一个非问号位置是索引2，字符为a
• 倒序填充索引1：选和a不同的b
• 填充索引0：选和b不同的a
• 最终得到ababb，符合题目要求
  以输入"?aa"为例：
• 第一个非问号位置是索引1，字符为a
• 倒序填充索引0：选和a不同的b
• 得到baa，没有违规子串，符合要求

复杂度说明 #

整个过程仅需要2-3次线性遍历字符串，时间复杂度为O(n)，空间复杂度为O(n)（仅存储字符列表），可以轻松处理n=5e5的最大规模用例。

内容的提问来源于stack exchange，提问作者infernus-85