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 <= 1051 <= str2.length <= 105str1 and str2 consist of only lowercase English letters.This approach uses two pointers to simultaneously traverse both strings. The goal is to see if `str2` can be formed as a subsequence of `str1` with at most one cyclic increment operation. During the traversal, if `str1[i]` can be incremented to match `str2[j]` by a cyclic shift, move both pointers forward. If `str1[i]` cannot be shifted to match `str2[j]`, and only one operation is allowed, then return false. Otherwise, continue checking until either `str2` is fully traversed (return true) or `str1` is exhausted (return false).
This C solution uses two indices, `i` and `j`, to iterate through `str1` and `str2`. It checks if a character in `str1` directly matches with or is a cyclic increment of a character in `str2`. If a match is found, we move to the next character in `str2`. If the end of `str2` is reached, it means it's possible to form `str2` as a subsequence.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of `str1` and m is the length of `str2` since we process each character once.
Space Complexity: O(1), since no additional space proportional to input size is used.
This method determines the feasibility of forming `str2` as a subsequence by transforming `str1` using character frequency transitions, considering cyclic alphabet rules. Using a frequency map for `str1`, iterate through `str2`, checking if corresponding increments can map `str1` characters to those in `str2`. For each character needed in `str2`, see if it's obtainable via allowable operations on `str1` characters, optimizing through potential full rotations using the alphabet cycle property.
The C solution leverages character counting: a frequency array tracks occurrences of each `str1` character. Each `str2` character checks whether direct presence or cyclic traversal can fulfill its emergence in `str1`. Absence discontinues success, embracing incremental dispatches.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m + 26) to cover all characters and frequency evaluations.
Space Complexity: O(1), preserving essential space outside of constant size arrays.
| Approach | Complexity |
|---|---|
| Approach 1: Two Pointer Technique | Time Complexity: O(n + m), where n is the length of `str1` and m is the length of `str2` since we process each character once. |
| Approach 2: Character Frequency Analysis | Time Complexity: O(n + m + 26) to cover all characters and frequency evaluations. |
Make String a Subsequence Using Cyclic Increments | Similar Problem |Leetcode 2825 |codestorywithMIK • codestorywithMIK • 5,106 views views
Watch 9 more video solutions →Practice Make String a Subsequence Using Cyclic Increments with our built-in code editor and test cases.
Practice on FleetCode