Problem of The Day: Make String a Subsequence Using Cyclic Increments

Problem Statement

Intuition

The problem involves checking whether one string (str2) can be derived as a subsequence of another string (str1) using specific transformation rules. A character from str1 can either match directly with the corresponding character in str2 or transform to match if it cycles to the next character in a circular alphabet fashion ('z' transforms to 'a').

The intuition is to traverse both strings and leverage the transformation rules to align characters. If we can exhaust all characters in str2 by moving through str1, the answer is True.

Approach

1. Use two pointers, i and j, to traverse str1 and str2, respectively.
2. For each pair of characters c1 (from str1) and c2 (from str2), check if:
   • c1 == c2 (direct match), or
   • (ord(c1) + 1) % 26 == ord(c2) % 26 (transformation match).
3. If a match is found, increment both pointers; otherwise, move the str1 pointer (i) forward to skip unmatched characters.
4. If the j pointer traverses all characters of str2, return True because str2 is a valid subsequence.
5. If not, verify the remaining unmatched portion of str2 to ensure they can all be derived via transformations.
6. Return False if any mismatch remains.

Complexity

• Time complexity: \(O(n)\), where \(n\) is the length of str1. The algorithm iterates through str1 and str2 using two pointers, ensuring a single pass through str1 in the worst case.
• Space complexity: \(O(1)\), as no additional data structures are used apart from a few variables.

Code

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i, j = 0, 0
        while i < len(str1) and j < len(str2):
            c1, c2 = str1[i], str2[j]
            if str1[i] == str2[j] or ((ord(c1) + 1) % 26) == ord(c2) % 26:
                i += 1
                j += 1
            else:
                i += 1

        if j == len(str2):
            return True

        for i in range(len(str1)):
            c1, c2 = str1[i], str2[j]
            if ((ord(c1) + 1) % 26) != ord(c2) % 26:
                return False

        return True

Editorial

Approach 2: Optimized Single Pass (Two Pointer)

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        str2_index = 0
        length_str1, length_str2 = len(str1), len(str2)

        # Traverse through both strings using a for loop
        for str1_index in range(length_str1):
            if str2_index < length_str2 and (
                str1[str1_index] == str2[str2_index]
                or ord(str1[str1_index]) + 1 == ord(str2[str2_index])
                or ord(str1[str1_index]) - 25 == ord(str2[str2_index])
            ):
                # If match found, move to next character in str2
                str2_index += 1

        # Check if all characters in str2 were matched
        return str2_index == length_str2