2825. Make String a Subsequence Using Cyclic Increments

Problem

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.

Solution (Java)

class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int i = 0;
        for (char c : str2.toCharArray()) {
            char t = (c == 'a') ? 'z' : (char) (c - 1);
            while (i < str1.length() && (str1.charAt(i) != c && str1.charAt(i) != t))  i++;
            if (i >= str1.length()) return false;
            i++;
        }
        return true;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).