• Leetcode POTDs

Problem 2825 Make String a Subsequence Using Cyclic Increments

Problem Statement

Link - Problem 2825

Question

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

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int i = 0;
        for(char ch:str1){
            if(i == str2.size())
                break;
            int a = ch -'a', b = str2[i]-'a';
            if(a==b || (a+1)%26 == b)
                i++;
        }
        return i == str2.size();

    }
};

Complexity Analysis

| Algorithm                    | Time Complexity | Space Complexity |
| ---------------------------- | --------------- | ---------------- |
| Two-pointer pattern matching | O(n)            | O(1)             |

Explanation

Intial Thoughts

When approaching this problem, consider the constraints given, such as the 0-indexed strings and the cyclic nature of the operation. Think of the relationship between the characters in str1 and str2. Observe how many characters in str2 can be formed from str1 using the operation. Consider how the length of str1 and str2 affect the outcome.

Intuitive Analysis

To intuitively solve this problem, imagine putting str1 and str2 side by side to compare their characters. Picture the characters in str1 shifting one position forward, wrapping around from ‘z’ to ‘a’, and see if this shift can make str2 a subsequence of str1. Consider how the characters in str2 match those in str1, with or without the shift, and think about how this match can be exploited to form str2 as a subsequence of str1.

1. Intuition

• The problem can be solved by iterating through str1 and checking if the current character matches the current character in str2 or if it can be incremented to match it.
• We only need to perform the operation at most once, so we can simply check if the current character in str1 can be incremented to match the current character in str2.
• If we find a match, we can move on to the next character in str2.
• If we reach the end of str2, it means we have found all the characters in str2 in str1, so we can return true.
• If we reach the end of str1 without finding all the characters in str2, it means we cannot make str2 a subsequence of str1, so we can return false.
• This solution works because it checks all possible matches between str1 and str2 in a single pass.
• The time complexity of this solution is O(n), where n is the length of str1.

2. Implementation

• We start by initializing a variable i to 0, which will keep track of the current position in str2.
• We then iterate through each character ch in str1.
• For each character, we check if i is equal to the size of str2, in which case we can break out of the loop.
• We calculate the ASCII values of ch and the current character in str2, and check if they are equal or if ch can be incremented to match the current character in str2.
• If they match, we increment i to move on to the next character in str2.
• Finally, we return true if i is equal to the size of str2, and false otherwise.
• The key code snippet is if(a==b || (a+1)%26 == b) i++;, which checks if the current character in str1 can be incremented to match the current character in str2.

Complexity Analysis

Time Complexity:

• The algorithm iterates through the string str1 using a single loop, hence the time complexity is directly proportional to the size of str1.
• Inside the loop, the operations performed, including the subtraction, comparison, and increment operations (int a = ch -'a', b = str2[i]-'a'; if(a==b || (a+1)%26 == b) i++) take constant time.
• Since the loop runs at most n times (where n is the length of str1), and each iteration takes constant time, the time complexity is O(n). There are no worst, average, or best case scenarios as the time complexity remains the same for all cases.

Space Complexity:

• The algorithm uses a constant amount of space to store the indices i, a, and b, regardless of the input size.
• No additional data structures are used that scale with input size, so space complexity is constant.
• Hence, the space complexity is O(1), as it does not grow with the size of the input strings.

Footnote

This question is rated as Medium difficulty.

Hints

Consider the indices we will increment separately.

We can maintain two pointers: pointer i for str1 and pointer j for str2, while ensuring they remain within the bounds of the strings.

If both str1[i] and str2[j] match, or if incrementing str1[i] matches str2[j], we increase both pointers; otherwise, we increment only pointer i.

It is possible to make str2 a subsequence of str1 if j is at the end of str2, after we can no longer find a match.

Similar Questions: