Salesforce 双字符串题：既是 x 的子序列又是 y 的子串

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入为两个字符串，返回最大长度；空串时返回 0。按 Python 字符迭代处理 Unicode code point，若面试平台按字节或 grapheme cluster 计数须另确认。
• 可以删除 x 中任意字符，保持剩余字符原顺序；在 y 中选的是连续片段。题目只求长度，不必返回片段或索引。
• 不限制同一个字符在 x 中出现次数，但一次匹配必须使用递增的 x 下标；单个 y 起点的候选只能向右延伸。

解题路线

1. 固定 y 的起点 s。目标是找到 y[s:] 中尽可能长的前缀，使其能作为 x 的子序列。扫描 x，维护 next_y 指向下一个必须匹配的 y 字符；相等才推进 next_y，不相等则跳过当前 x 字符。
2. 贪心正确性：对于固定前缀，第 k 个所需字符选择 x 中最早可用位置，不会减少后续匹配的可用后缀；若最早位置之后都无法匹配，任何更晚的选择也不能成功。因而一次扫描得到该起点的最长可行前缀。
3. 枚举 y 的全部起点并取最大值，覆盖了每个可能的 y 子串。与常见 LCS 不同，不能在 y 内跳字符；也不能仅求最长公共子串，因为 x 允许跳字符。

手动走一遍

x=hackerranks，y=hackers。起点 s=0 时依次匹配 h,a,c,k,e,r,s；x 中多余的 r、a、n、k 可跳过，得到长度 7。若 x=abcd，y=abdc，选择 y 的片段 abd，x 中跳过 c，答案为 3。若 x 为空或 y 为空，枚举或扫描没有匹配，返回 0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def longest_subsequence_also_substring(x: str, y: str) -> int:
    """Maximum length of a subsequence of x that is contiguous in y."""
    best = 0
    for start in range(len(y)):
        next_y = start
        for char in x:
            if next_y < len(y) and char == y[next_y]:
                next_y += 1
                if next_y == len(y):
                    break
        best = max(best, next_y - start)
    return best

复杂度

设 n=|x|、m=|y|。对 m 个起点各扫描至多 n 个字符，时间 O(nm)；只维护起点、y 指针与答案，辅助空间 O(1)。当 m、n 在题目所述约 2000 量级时，约 400 万次字符检查属于可讨论的训练规模；实际平台时限仍需测量。

易错点与追问

容易失分的边界

• 把 x 和 y 都当作子序列，得到普通 LCS，却允许在 y 中跳字符。
• 把两者都当作子串，错过 x 中需要跳字符的最优答案。
• 对固定 y 起点遇到 x 不匹配就停止；x 的字符允许跳过，只有 y 必须连续。
• 只保存每个 y 位置的 LCS 长度而不维护 y 连续段的起点，导致 DP 状态含义混乱。

继续深挖

• 若要求返回具体 y 子串，记录最佳起点与长度；若同长需按最早起点或字典序选，先确认规则。
• 若同一 x 要对许多 y 查询，可预处理 x 的字符位置索引或 next-occurrence 表；代价是额外空间，收益取决于字符集和查询量。
• 若 n、m 远超 2000，可讨论位集、字符位置跳转或特殊字符集优化，但先给出明确复杂度和适用条件。