Watch 10 video solutions for Make String a Subsequence Using Cyclic Increments, a medium level problem involving Two Pointers, String. This walkthrough by codestorywithMIK has 5,941 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |