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 makestr2 a subsequence ofstr1 by performing the operationat 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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5
6

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

1
2
3
4

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 <= 10^5
  • 1 <= str2.length <= 10^5
  • str1 and str2 consist of only lowercase English letters.

Solution

Method 1 - Two Pointer Technique

The intuition behind this code lies in the idea of transforming characters in one string to match characters in another string, effectively determining if the second string can be formed as a subsequence of the first string through specific transformations.

The code aims to compare characters from both strings and checks for conditions under which a character from the second string can be matched to a character in the first string or transformed to match it.

The code specifically handles two scenarios for character transformation:

  1. Exact matching: Where the characters in both strings are the same.
  2. Matching with an incremented value cyclically: Where the character in str1 is incremented by one place in the alphabet (‘a’ becomes ‘b’, ‘b’ becomes ‘c’, …, and ‘z’ becomes ‘a’). Here is the approach:
  3. Initialization:
    • The code initializes two pointers i and j to keep track of the current positions in the strings str1 and str2, respectively.
    • It also calculates the lengths of both strings, but instead of storing them, we use their direct lengths for simplicity.
  4. Looping Through Strings:
    • The code enters a while loop that iterates as long as there are characters left to be compared in both str1 and str2 (i.e., i is less than str1.length() and j is less than str2.length()).
  5. Character Comparison and Transformation:
    • Inside the loop, the code performs two types of comparisons between characters of str1 and str2:
      • str1[i] == str2[j]: It checks if the current characters at positions i and j are the same.
      • (str1[i] - 'a' + 1) % 26 + 'a' == str2[j]: It checks if the character at str1[i] incremented by 1 cyclically is equal to the character at str2[j].
    • If any of these conditions are met, it means that the current character in str2 can be matched to a character in str1 after performing certain transformations. In this case, the code increments the j pointer to move to the next character in str2.
  6. Pointer Advancement:
    • After the comparison and possible transformation, the code increments the i pointer to move to the next character in str1.
  7. Result Evaluation:
    • After the loop, the code checks whether the j pointer has reached the end of str2 (i.e., j is equal to str2.length()).
    • If it has, it means all characters in str2 were found as subsequences in str1 according to the specified transformations, so the function returns true.
    • Otherwise, it returns false.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int i = 0, j = 0;
        while (i < str1.length() && j < str2.length()) {
            char curr = str1.charAt(i);
            char transformed = (char) ((curr - 'a' + 1) % 26 + 'a');
            if (str1.charAt(i) == str2.charAt(j) || transformed == str2.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == str2.length();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i, j = 0, 0
        while i < len(str1) and j < len(str2):
            curr = str1[i]
            transformed = chr((ord(curr) - ord('a') + 1) % 26 + ord('a'))
            if str1[i] == str2[j] or transformed == str2[j]:
                j += 1
            i += 1
        return j == len(str2)

Complexity

  • ⏰ Time complexity: O(n + m) where n is the length of str1 and m is the length of str2.
  • 🧺 Space complexity:  O(1) as we are only using a few extra variables.