Make String a Subsequence Using Cyclic Increments

Medium

Asked by:

6 views

Topics:

StringsTwo PointersGreedy Algorithms

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible characters in the strings `s` and `t`, and is there a defined alphabet or character set to consider?
Can the strings `s` or `t` be empty or null?
If it's not possible to make `t` a subsequence of `s` using cyclic increments, what should I return (e.g., null, empty string, a boolean indicating failure)?
Are both strings guaranteed to contain only lowercase letters?
If there are multiple ways to make `t` a subsequence of `s`, is any valid solution acceptable?

Brute Force Solution

Approach

The brute force method tackles this problem by exploring every potential way to construct the desired subsequence. It systematically checks each possible character pairing to see if it fits the cyclic increment rule. It repeats until either a valid subsequence is found, or all possibilities have been exhausted.

Here's how the algorithm would work step-by-step:

Start by considering the first character of the target subsequence.
Check if the initial character of the original string matches the first character of the subsequence, or if the original string's character can be transformed into the target character using the cyclic increment rule. If a match is impossible, there is no subsequence.
If a match is found, move to the second character of the subsequence.
Now, for the remaining characters of the original string (after the index we previously found the match), check if any of them match the second character of the subsequence or can be transformed into it.
Continue this process for each character in the subsequence, always looking for a suitable match in the original string after the last match we found.
If, at any point, you cannot find a matching character in the original string for a character in the subsequence, then the subsequence cannot be made.
If you successfully find a matching character in the original string for every character in the subsequence, then the subsequence can be made.

Code Implementation

def can_make_subsequence(original_string, subsequence):
    original_string_length = len(original_string)
    subsequence_length = len(subsequence)
    original_string_index = 0
    subsequence_index = 0

    while subsequence_index < subsequence_length:
        # If we've exhausted the original string, subsequence can't be made
        if original_string_index >= original_string_length:
            return False

        original_char = original_string[original_string_index]
        subsequence_char = subsequence[subsequence_index]

        # Check if characters are equal or can be made equal
        if original_char == subsequence_char or \
           (ord(original_char) - ord('a') + 1) % 26 == (ord(subsequence_char) - ord('a')) % 26:

            # Move to next char in subsequence upon a match
            subsequence_index += 1

        # Always increment through original string characters
        original_string_index += 1

    # If we reach end of subsequence, it is a valid subsequence
    return True

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the length of the original string and m be the length of the target subsequence. The brute force method iterates through the target subsequence (length m). For each character in the subsequence, it searches through the original string (length n) from the last matched index onward. Thus, in the worst case, for each of the m characters in the target, we might iterate through nearly all n characters of the original string. This gives a time complexity of O(n*m).

Space Complexity

O(1) – The brute force approach, as described, primarily iterates through the strings using index variables. It does not create any auxiliary data structures like lists, hash maps, or stacks to store intermediate results or track visited states. Therefore, the algorithm's space usage remains constant and independent of the input string sizes; it only uses a few variables to keep track of the current positions. The space complexity is O(1).

Optimal Solution

Approach

The goal is to see if we can construct a string from another by only incrementing letters cyclically (a -> b, b -> c, ..., z -> a). We go through both strings character by character, trying to match them. The key is to only increment when necessary and always in the smallest number of steps.

Here's how the algorithm would work step-by-step:

Start by comparing the first characters of both strings.
If the characters are the same, move to the next character in both strings.
If the character in the first string comes before the character in the second string, check if we can reach the second character by incrementing the first.
If we can, move to the next character in both strings.
If the character in the first string comes after the character in the second string, check if we can reach the second character by wrapping around from 'z' to 'a'.
If we can reach the character in the second string by wrapping, move to the next character in both strings.
If at any point we cannot make the character in the first string match the character in the second string through cyclic increments, the answer is no; we can't make the first string a subsequence of the second.
If we get through the entire second string, it means we were able to find a match for every character in the second string as a subsequence of the first string. Return yes.

Code Implementation

def is_subsequence_by_increment(main_string, sub_string):
    main_string_index = 0
    sub_string_index = 0

    while sub_string_index < len(sub_string) and main_string_index < len(main_string):
        if main_string[main_string_index] == sub_string[sub_string_index]:
            main_string_index += 1
            sub_string_index += 1

        else:
            #Check if we can increment to the substring character
            if main_string[main_string_index] < sub_string[sub_string_index]:
                if ord(sub_string[sub_string_index]) - ord(main_string[main_string_index]) > 0:
                    main_string_index += 1

                else:
                    return False

            else:
                # Check if we can wrap around to reach substring char
                if ord(sub_string[sub_string_index]) - ord(main_string[main_string_index]) + 26 > 0:
                    main_string_index += 1

                else:
                    return False

    #If we reached the end of substring, then its a subsequence
    if sub_string_index == len(sub_string):
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through both strings, 'string1' and 'string2', character by character using a single while loop. In the worst-case scenario, the while loop continues until the end of 'string2' is reached, which has a length of 'n'. Inside the loop, we perform constant-time operations (character comparison and increment checks). Therefore, the time complexity is directly proportional to the length of 'string2', resulting in O(n) time complexity, assuming 'string2' is the longer string and its length is represented by 'n'.

Space Complexity

O(1) – The algorithm iterates through the input strings using a constant number of index variables. No additional data structures, such as arrays, lists, or hash maps, are used to store intermediate results or track visited characters. Therefore, the space required by the algorithm remains constant, irrespective of the length of the input strings. The space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty source string	Return true if the target string is also empty, otherwise return false as an empty source cannot form a non-empty target.
Null or empty target string	Return true, because an empty target string is always a subsequence of any source string.
Source string shorter than target string	Return false, as the target string cannot be a subsequence if it's longer than the source.
Source and target strings are identical	Return true, as any string is a subsequence of itself (the trivial subsequence).
Characters in target string are not cyclically incrementable from any character in source	Return false, as the target string characters cannot be formed by cyclic increments.
Large source string	The solution should iterate through the source string at most once, so the time complexity is O(n) where n is the length of the source string, making it efficient.
Source string with repeating characters, but target needs specific order	The algorithm needs to maintain the correct order during the cyclic increment checks to ensure subsequence validity.
Source string contains characters that are beyond the range of a-z	The cyclic increment logic should handle wrapping around from 'z' to 'a' correctly and throw an exception if characters outside a-z are found.

Null or empty source string

How to Handle:

Return true if the target string is also empty, otherwise return false as an empty source cannot form a non-empty target.

Null or empty target string

How to Handle:

Return true, because an empty target string is always a subsequence of any source string.

Source string shorter than target string

How to Handle:

Return false, as the target string cannot be a subsequence if it's longer than the source.

Source and target strings are identical

How to Handle:

Return true, as any string is a subsequence of itself (the trivial subsequence).

Characters in target string are not cyclically incrementable from any character in source

How to Handle:

Return false, as the target string characters cannot be formed by cyclic increments.

Large source string

How to Handle:

The solution should iterate through the source string at most once, so the time complexity is O(n) where n is the length of the source string, making it efficient.

Source string with repeating characters, but target needs specific order

How to Handle:

The algorithm needs to maintain the correct order during the cyclic increment checks to ensure subsequence validity.

Source string contains characters that are beyond the range of a-z

How to Handle:

The cyclic increment logic should handle wrapping around from 'z' to 'a' correctly and throw an exception if characters outside a-z are found.