[LeetCode] 2825. Make String a Subsequence Using Cyclic Increments

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is ‘a’ becomes ‘b’, ‘b’ becomes ‘c’, and so on, and ‘z’ becomes ‘a’.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:
Input: str1 = “abc”, str2 = “ad”
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become ‘d’.
Hence, str1 becomes “abd” and str2 is now a subsequence. Therefore, true is returned.

Example 2:
Input: str1 = “zc”, str2 = “ad”
Output: true
Explanation: Select indices 0 and 1 in str1.
Increment str1[0] to become ‘a’.
Increment str1[1] to become ‘d’.
Hence, str1 becomes “ad” and str2 is now a subsequence. Therefore, true is returned.

Example 3:
Input: str1 = “ab”, str2 = “d”
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once.
Therefore, false is returned.

Constraints:
1 <= str1.length <= 105
1 <= str2.length <= 105
str1 and str2 consist of only lowercase English letters.

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

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

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

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

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

思路

思路是同向双指针，一个指针指向 str1，一个指针指向 str2。如果str1[i] == str2[j]，则 i 和 j 同时向后移动，直到 str1[i]!= str2[j]。当 str1[i]!= str2[j] 的时候，因为题目只允许我们修改 str1 中的字符，所以我们只能移动 i 指针，判断他是否能和 str2[j] 相等。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        // corner case
        if (n > m) {
            return false;
        }

        // normal case
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            char a = str1.charAt(i);
            char b = str2.charAt(j);
            if (a == b || (a + 1 - 'a') % 26 == b - 'a') {
                j++;
            }
            i++;
        }
        if (j == n) {
            return true;
        }
        return false;
    }
}