We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make String a Subsequence Using Cyclic Increments

Number: 3018

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given two 0-indexed strings str1 and str2, determine if it is possible to make str2 a subsequence of str1 by performing at most one operation. In the operation, you can choose any set of indices in str1 and increment each selected character to its next character cyclically (i.e. 'a' becomes 'b', …, 'z' becomes 'a'). A subsequence is obtained by deleting some characters (possibly none) without changing the order of the remaining characters.

Key Insights

  • You are allowed at most one operation that can increment characters at any set of indices (each at most once).
  • Each character in str1 can effectively have two possibilities: its original value or its next cyclic character.
  • The subsequence matching can be solved with a two-pointer greedy approach: for each character in str1, check if either the original or the incremented value can match the current character in str2.
  • If str2 is already a subsequence (i.e. matching by original letters), answer is true, otherwise a mix of original and incremented letter usage can be applied.
  • The decision for each character is independent (since the operation is “global”, all needed increments can be done simultaneously).

Space and Time Complexity

Time Complexity: O(n) where n is the length of str1 (we scan through str1 once).
Space Complexity: O(1) extra space.

Solution

The solution uses a two-pointers technique. One pointer iterates over str1 and the other over str2. For each character in str1, we check both possibilities:

  1. If the character as-is matches the current target character in str2, we move the target pointer forward.
  2. If not, we check if the incremented (cyclic next) version of the character equals the current target character. If it does, we also move the target pointer forward. Since any index in str1 can be chosen for the increment operation (and doing so once is allowed), these checks cover the only two possibilities for making a match. If we can match all characters in str2 in order, then str2 is a possible subsequence of str1 after at most one operation.

This greedy approach guarantees that if there exists any valid set of choices (using no operation or using increments where necessary) to form str2 as a subsequence, it will be found in one pass.

Code Solutions

# Python solution: Two-pointer approach
def canMakeSubsequence(str1: str, str2: str) -> bool:
    # pointer for str2 subsequence matching
    j = 0
    n2 = len(str2)
    
    # iterate through every character in str1
    for char in str1:
        # if we have already matched all characters in str2, break early
        if j == n2:
            break
        
        # check if current character matches target directly
        if char == str2[j]:
            j += 1
        # otherwise, check if incrementing the character (cyclically) matches target
        elif (ord(char) - ord('a') + 1) % 26 + ord('a') == ord(str2[j]):
            j += 1
    # if j reached the end, then all characters of str2 are matched
    return j == n2

# Example usage:
print(canMakeSubsequence("abc", "ad"))  # Expected output: True
← Back to All Questions