What is the main technique for solving the "Make String a Subsequence Using Cyclic Increments" problem?

The primary technique is using two-pointer scanning with invariant tracking to match characters of str2 to str1, applying cyclic increments when needed.

How do you apply cyclic increments to the characters in str1?

Cyclic increments involve selecting indices of str1 and changing each character to the next one in the alphabet, where 'z' wraps around to 'a'.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of str1, since we perform a single pass over both strings.

Can this problem be solved using dynamic programming?

While dynamic programming is not necessary for this problem, two-pointer scanning with careful tracking of increments is the most efficient solution.

What happens if str1 and str2 are already subsequences?

If str1 already contains str2 as a subsequence, the function should return true without any operations, as no increment is required.

#2825

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

循环增长使字符串子序列等于另一个字符串

给你一个下标从 0 开始的字符串 str1 和 str2 。一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环递增，变成下一个字符。也就是说 'a' 变成 'b' ， 'b' 变成 'c' ，以此类推， 'z' 变成 'a' 。如果执行以上操作 …

双指针字符串

题目描述

给你一个下标从 0 开始的字符串 str1 和 str2 。

一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环递增，变成下一个字符。也就是说 'a' 变成 'b' ，'b' 变成 'c' ，以此类推，'z' 变成 'a' 。

如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。

注意：一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。

示例 1：

输入：str1 = "abc", str2 = "ad"
输出：true
解释：选择 str1 中的下标 2 。
将 str1[2] 循环递增，得到 'd' 。
因此，str1 变成 "abd" 且 str2 现在是一个子序列。所以返回 true 。

示例 2：

输入：str1 = "zc", str2 = "ad"
输出：true
解释：选择 str1 中的下标 0 和 1 。
将 str1[0] 循环递增得到 'a' 。
将 str1[1] 循环递增得到 'd' 。
因此，str1 变成 "ad" 且 str2 现在是一个子序列。所以返回 true 。

示例 3：

输入：str1 = "ab", str2 = "d"
输出：false
解释：这个例子中，没法在执行一次操作的前提下，将 str2 变为 str1 的子序列。
所以返回 false 。

提示：

1 <= str1.length <= 10⁵
1 <= str2.length <= 10⁵
str1 和 str2 只包含小写英文字母。

lightbulb

解题思路

方法一：双指针

本题实际上需要我们判断一个字符串 $s$ 是否为另一个字符串 $t$ 的子序列，只不过字符之间可以不完全匹配，如果两个字符相同，或者一个字符是另一个字符的下一个字符，就可以匹配。

时间复杂度 $O(m + n)$ ，其中 $m$ 和 $n$ 分别是字符串 $str1$ 和 $str2$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i = 0
        for c in str1:
            d = "a" if c == "z" else chr(ord(c) + 1)
            if i < len(str2) and str2[i] in (c, d):
                i += 1
        return i == len(str2)

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of two-pointer techniques and cyclic operations.
question_mark
Check if the candidate can efficiently match characters using one operation.
question_mark
Evaluate if they understand the invariant tracking to align the two strings.

warning

常见陷阱

外企场景

error
Misunderstanding the cyclic increment operation and assuming non-cyclic transformations are sufficient.
error
Attempting to apply more than one operation when the problem only allows a single increment.
error
Failing to maintain the invariant correctly, which could lead to an incorrect result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if str1 is already a subsequence of str2?
arrow_right_alt
What if the cyclic increment must occur multiple times for different characters?
arrow_right_alt
How does the solution change if we allow more than one operation?

help

常见问题

外企场景

继续练习

#2911 得到 K 个半回文串的最少修改次数 #2938 区分黑球与白球 #2697 字典序最小回文串