2026-10-08：一次替换后的子序列。用go语言，给定两个只包含小写字母的字符串 s 和 t。你可以在 s 中至多改动一个位置上的字符，把它换成任意一个小写字母。问经过这样的至多一次改动后，能否让

2026-10-08：一次替换后的子序列。用go语言，给定两个只包含小写字母的字符串 s 和 t。你可以在 s 中至多改动一个位置上的字符，把它换成任意一个小写字母。问经过这样的至多一次改动后，能否让 s 按原有先后顺序出现在 t 中。也就是说，能否从 t 里删掉一些字符后，得到完整的 s；只要求字符顺序一致，不要求连续。如果能够做到，结果为 true；否则为 false。

1 <= s.length, t.length <= 100000。

s 和 t 仅由小写英文字母组成。

输入： s = “cat”, t = “chat”。

输出： true。

解释：

将 s[1] 从 ‘a’ 替换为 ‘h’，得到字符串 “cht”。

“cht” 是 “chat” 的子序列，因为可以按顺序匹配 ‘c’、‘h’ 和 ‘t’。

题目来自力扣3983。

大体步骤如下：

• 状态一：表示完全没有使用过修改机会时，s 的前面已经有多少个字符成功按顺序匹配到了 t 的当前前缀中。
• 状态二：表示最多使用一次修改机会时，s 的前面已经有多少个字符成功按顺序匹配到了 t 的当前前缀中。这里“最多一次”可以是一次都没用，也可以是已经用掉了那唯一的一次修改。

一开始，两个状态都从 0 开始，表示还没有匹配任何字符。如果 s 的长度比 t 还长，那肯定不可能成为子序列，直接返回 false。

然后从左到右依次扫描 t 中的每一个字符。对于当前字符，会做几件事：

如果 t 的所有字符都扫描完了，这个状态仍然没有达到 s 的总长度，说明无法做到，返回 false。

用例子 s = “cat”，t = “chat” 来看：

• 初始两个状态都是 0。
• 遇到 t 的 ‘c’：s 的第一个字符也是 ‘c’，所以两个状态都可以正常前进，都变成 1。
• 遇到 ‘h’：s 的第二个字符是 ‘a’，不等于 ‘h’。未用修改的状态不能前进，仍然是 1。但已用修改的状态可以借助修改机会，把 s 的第二个字符 ‘a’ 改成 ‘h’，于是这个状态推进到 2。
• 遇到 ‘a’：已用修改的状态当前待匹配的是 s 的第三个字符 ‘t’，不等于 ‘a’，不能正常前进；但它已经用过一次修改，不能再改，所以保持 2。未用修改的状态此时待匹配的是 s 的第二个字符 ‘a’，正好等于 ‘a’，所以前进到 2。
• 遇到 ‘t’：已用修改的状态待匹配的是 s 的第三个字符 ‘t’，正好等于 ‘t’，于是前进到 3。此时已达到 s 的总长度 3，返回 true。

整个过程中，只遍历了 t 一次，每个字符只做了常数次比较和更新操作，所以总的时间复杂度是 O(t 的长度)。额外使用的变量只有几个整数状态，不随字符串长度增长，所以总的额外空间复杂度是 O(1)。

Go完整代码如下：

package main

import (
"fmt"
)

func canMakeSubsequence(s, t string) bool {
n := len(s)
if n > len(t) {
return false
}

j0 := 0 // 在不修改的情况下，s 的前缀 [0, j0-1] 是 t 的当前前缀的子序列
j1 := 0 // 在改过一次的情况下，s 的前缀 [0, j1-1] 是 t 的当前前缀的子序列
for _, ch := range t {
// j1 普通匹配
if s[j1] == byte(ch) {
j1++
}

// 也可以修改 s[j0] 为 ch，强行匹配
j1 = max(j1, j0+1)

// j0 普通匹配
if s[j0] == byte(ch) {
j0++
}

if j1 == n {
// s 是 t 的子序列
return true
}
}
return false
}

func main() {
s := "cat"
t := "chat"
result := canMakeSubsequence(s, t)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def canMakeSubsequence(s: str, t: str) –> bool:
n = len(s)
if n > len(t):
return False

if n == 0:
return True

j0 = 0 # 不修改时，s 的前缀 [0, j0-1] 已匹配
j1 = 0 # 最多修改一次时，s 的前缀 [0, j1-1] 已匹配

for ch in t:
# j1 尝试正常匹配
if j1 < n and s[j1] == ch:
j1 += 1

# 也可以把 s[j0] 修改为 ch，强行多匹配一个字符
j1 = max(j1, j0 + 1)

# j0 尝试正常匹配
if j0 < n and s[j0] == ch:
j0 += 1

if j1 == n:
return True

return False

if __name__ == "__main__":
s = "cat"
t = "chat"
result = canMakeSubsequence(s, t)
print(result)

C++完整代码如下：

#include <iostream>
#include <string>
#include <algorithm>

bool canMakeSubsequence(const std::string& s, const std::string& t) {
int n = static_cast<int>(s.size());
if (n > static_cast<int>(t.size())) {
return false;
}
if (n == 0) {
return true;
}

int j0 = 0; // 不修改时，s 的前缀 [0, j0-1] 已匹配
int j1 = 0; // 最多修改一次时，s 的前缀 [0, j1-1] 已匹配

for (char ch : t) {
// j1 尝试正常匹配
if (j1 < n && s[j1] == ch) {
++j1;
}

// 也可以把 s[j0] 修改为 ch，强行多匹配一个字符
if (j0 < n) {
j1 = std::max(j1, j0 + 1);
}

// j0 尝试正常匹配
if (j0 < n && s[j0] == ch) {
++j0;
}

if (j1 == n) {
return true;
}
}
return false;
}

int main() {
std::string s = "cat";
std::string t = "chat";
bool result = canMakeSubsequence(s, t);
std::cout << std::boolalpha << result << std::endl;
return 0;
}