Google OA 题解｜只能改一个字符，子序列为什么要留两种状态

Google 这道历史 OA 字符串题允许修改目标串的一个字符，但第一个字符不能动。限制只有一句，直接遇到不匹配就修改，却会把机会用错。题目出自 2024 年的 第一题记录 ，未标注地区；这里讨论这一题，不扩展成整套笔试。

第一题：修改一次后，能否匹配子序列

题目描述

给定非空字符串 A、B，允许修改 B 中至多一个非首位字符，判断修改后的 B 能否成为 A 的子序列。成功返回起始位置，失败返回 -1。下标从 1 开始；练习实现约定多解时返回最早起点。 自拟例子：A 为 acbd，B 为 abe，可以选 A 的第 1、3、4 位，把 B 末尾的 e 改成 d，返回 1。如果 A 为 xbcd，B 为 abcd，则返回 -1：首字符 a 不能改成 x。

解题思路

先找 A 中第一个等于 B[0] 的位置 s。没有就返回 -1；B 长度为 1 就返回 s+1。起点不必逐个尝试：任何更晚起点能用的后续字符，s 后面也都能用。 从 s 后面扫描，只保留两个数。p 表示完全不修改时，最多匹配了 B 的多少个字符；q 表示至多修改一次时，最多匹配了多少个字符。两者初始值都是 1。同样的修改预算下，匹配得更长的前缀足够代表当前进度。 处理字符 c 时，先保存旧的 p、q。q 有三种选择：跳过 c；如果 c 等于 B[q]，沿原状态前进一步；从旧 p 出发，把 B[p] 改成 c，前进一步。取最大值。p 只在 c 等于 B[p] 时加一。所有数组访问都先检查下标小于 B 的长度，且每次转移只用旧状态。 不能先增加 p，再拿新 p 更新 q，否则同一个 A 字符会被使用两次。扫描中 q 达到 B 的长度就成功；扫描完还没达到则失败。 复杂度 ：时间 O(|A|+|B|)，额外空间 O(1)，这里不返回完整匹配路径。

Google OA 练习如何检查

把目标长度为 1、首字符不存在、零次修改就能匹配、必须留到最后才修改这几类输入分别跑过。短串可以枚举 A 的所有等长子序列，检查首位一致、其余位置至多一处不同，再和优化结果比较。 美国 New Grad 的两份记录各有不同细节：Reddit 作者在 2024 年 9 月完成两道 OA 编程题，之后进入面试；Taro 的 2025 年 2 月记录提到个人约二十分钟完成测评。二十分钟是该候选人的用时，不能当成考试时限，这两份记录也没有将上述子序列题列为原题。

FAQ

子序列需要连续吗？

不需要。可以跳过 A 的字符，但选中位置的先后顺序不能改变。

为什么保留不修改的状态？

它把修改机会留给后面的字符。只保留一条贪心路径，会丢掉这条分支。

能直接输出匹配的所有下标吗？

这套常数空间状态只判断可行性并返回起点。要输出完整路径，需要另外保存转移信息，或采用能恢复路径的动态规划。

参考来源

LeetCode：Google OA 2024 第一题 Reddit：美国 New Grad 从 OA 到 Team Matching Taro：美国 SWE New Grad 测评经历

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。