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.Problem Overview: You are given two strings str1 and str2. You may increment any character in str1 by one cyclic step ('z' → 'a'). The task is to determine whether str2 can become a subsequence of the modified str1.
Approach 1: Two Pointer Technique (O(n) time, O(1) space)
This problem fits naturally with the two pointers pattern used for subsequence checks. Maintain pointer i for str1 and pointer j for str2. While scanning str1, check whether the current character already matches str2[j] or becomes equal after one cyclic increment. The cyclic increment can be computed as (c - 'a' + 1) % 26 + 'a'. If either condition matches, advance j. Always advance i. When j reaches the length of str2, the subsequence exists.
The key insight: each character in str1 has exactly two valid states for matching—its original value or its incremented value. Because subsequence order must be preserved, scanning once with two pointers guarantees correctness. This greedy check processes every character exactly once, giving O(n) time and constant extra space. It is the standard solution expected in interviews involving string traversal.
Approach 2: Character Frequency Analysis (O(n + m) time, O(1) space)
A secondary perspective is to analyze the possible characters each position in str1 can produce. For every character, consider both its original value and its cyclic successor. Instead of immediately matching positions, track whether required characters from str2 appear in order while validating that the needed character is reachable from the current str1 position. Conceptually this acts like a lightweight frequency feasibility check combined with sequential scanning.
This approach highlights the transformation constraint: every character can shift forward by exactly one step in the alphabet. During iteration, you compare the target character from str2 against the current character and its incremented version. The algorithm still performs a single pass over both strings, so the complexity remains O(n + m) time with O(1) space.
Recommended for interviews: The two pointer technique is the expected solution. It directly models subsequence matching and shows you recognize the greedy property of the cyclic increment rule. The frequency-style reasoning helps build intuition, but interviewers typically want to see the linear scan with pointer advancement because it is simpler, optimal, and easy to implement under time pressure.
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.
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.
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.
This problem actually requires us to determine whether a string s is a subsequence of another string t. However, the characters do not have to match exactly. If two characters are the same, or one character is the next character of the other, they can match.
The time complexity is O(m + n), where m and n are the lengths of the strings str1 and str2 respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| 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. |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Technique | O(n) | O(1) | Best general solution for checking subsequence with transformation rules |
| Character Frequency Analysis | O(n + m) | O(1) | Useful for reasoning about reachable characters before implementing greedy matching |
Make String a Subsequence Using Cyclic Increments | Similar Problem |Leetcode 2825 |codestorywithMIK • codestorywithMIK • 5,941 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