Make String a Subsequence Using Cyclic Increments solution and explanation
9 more videos on this problem
Make String a Subsequence Using Cyclic Increments | Similar Problem |Leetcode 2825 |codestorywithMIKcodestorywithMIK · 13:39 · 6K views
Make String a Subsequence Using Cyclic Increments | Leetcode 2825Techdose · 14:27 · 2K views
2825. Make String a Subsequence Using Cyclic Increments | 2 Pointers | Strings | GreedyAryan Mittal · 9:08 · 1K views
Leetcode BiWeekly contest 111 - Medium - Make String a Subsequence Using Cyclic IncrementsPrakhar Agrawal · 9:02 · 1K views
2825. Make String a Subsequence Using Cyclic Increments (Leetcode Medium)Programming Live with Larry · 7:44 · 532 views
LeetCode 2825 Make String a Subsequence Using Cyclic Increments | String | Two Pointers | AmazonCode Harmony · 15:10 · 269 views
leetcode 2825. Make String a Subsequence Using Cyclic Increments - two -pointer trickCode-Yao · 6:59 · 180 views
2825. Make String a Subsequence Using Cyclic Increments,Biweekly Contest 111Surajit Roy_Roll-50 · 13:20 · 81 views
Make String a Subsequence Using Cyclic Increments || leetCodeProgramming with niraj · 12:06 · 78 views
2825. Make String a Subsequence Using Cyclic Increments | C++ | Simple explanation | Leetcode | DSAAnshul Explains · 7:32 · 54 views
The problem
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 <= 105str1andstr2consist of only lowercase English letters.
Approach overview
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 1: Approach 1: Two Pointer Technique
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).
def can_form_subsequence(str1: str, str2: str) -> bool:
i = j = 0
n, m = len(str1), len(str2)
while i < n and j < m:
if str1[i] == str2[j] or chr((ord(str1[i]) - ord('a') + 1) % 26 + ord('a')) == str2[j]:
j += 1
i += 1
return j == mpublic class Solution {
public boolean canFormSubsequence(String str1, String str2) {
int i = 0, j = 0, n = str1.length(), m = str2.length();
while (i < n && j < m) {
if (str1.charAt(i) == str2.charAt(j) || (str1.charAt(i) - 'a' + 1) % 26 + 'a' == str2.charAt(j)) {
j++;
}
i++;
}
return j == m;
}
}#include <string>
using namespace std;
bool canFormSubsequenceByCyclicIncrement(string str1, string str2) {
int i = 0, j = 0, n = str1.size(), m = str2.size();
while (i < n && j < m) {
if (str1[i] == str2[j] || (((str1[i] - 'a' + 1) % 26 + 'a') == str2[j])) {
j++;
}
i++;
}
return j == m;
}function canFormSubsequence(str1, str2) {
let i = 0, j = 0, n = str1.length, m = str2.length;
while (i < n && j < m) {
if (str1[i] === str2[j] || String.fromCharCode((str1.charCodeAt(i) - 'a'.charCodeAt(0) + 1) % 26 + 'a'.charCodeAt(0)) === str2[j]) {
j++;
}
i++;
}
return j === m;
}#include <stdbool.h>
#include <string.h>
bool canFormSubsequenceByCyclicIncrement(char *str1, char *str2) {
int len1 = strlen(str1);
int len2 = strlen(str2);
int i = 0, j = 0;
while (i < len1 && j < len2) {
if (str1[i] == str2[j] || ((str1[i] - 'a' + 1) % 26 + 'a') == str2[j]) {
j++; // Increment str2 pointer
}
i++; // Always increment str1 pointer
}
return j == len2;
}public class Solution {
public bool CanFormSubsequence(string str1, string str2) {
int i = 0, j = 0, n = str1.Length, m = str2.Length;
while (i < n && j < m) {
if (str1[i] == str2[j] || (str1[i] - 'a' + 1) % 26 + 'a' == str2[j]) {
j++;
}
i++;
}
return j == m;
}
}This Python solution uses loop iteration and the `ord` function to perform cyclic checks on character indices. The code ever so slightly resembles a `two pointer technique`, ensuring every approved character contributes to forming a proper subsequence of `str2` from `str1`.
Time Complexity: O(n + m), iterating through each relevant character once.
Space Complexity: O(1), since no intricate data storage structures are used.
Approach 2: Approach 2: Character Frequency Analysis
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.
def can_form_subsequence_by_char_freq(str1: str, str2: str) -> bool:
char_count = [0] * 26
for char in str1:
char_count[ord(char) - ord('a')] += 1
for char in str2:
idx = ord(char) - ord('a')
if char_count[idx] > 0:
char_count[idx] -= 1
else:
can_transform = False
for j in range(26):
if char_count[j] > 0 and (chr((j + 1) % 26 + ord('a')) == char):
can_transform = True
char_count[j] -= 1
break
if not can_transform:
return False
return Trueimport java.util.HashMap;
public class Solution {
public boolean canFormSubsequenceByCharFreq(String str1, String str2) {
int[] charCount = new int[26];
for (char c : str1.toCharArray()) {
charCount[c - 'a']++;
}
for (char c : str2.toCharArray()) {
int idx = c - 'a';
if (charCount[idx] > 0) {
charCount[idx]--;
} else {
boolean canTransform = false;
for (int j = 0; j < 26; j++) {
if (charCount[j] > 0 && (((j + 1) % 26 + 'a') == c)) {
canTransform = true;
charCount[j]--;
break;
}
}
if (!canTransform) return false;
}
}
return true;
}
}#include <vector>
#include <string>
using namespace std;
bool canFormSubsequenceByCharFreq(string str1, string str2) {
vector<int> charCount(26, 0);
for (char c : str1) {
charCount[c - 'a']++;
}
for (char c : str2) {
int idx = c - 'a';
if (charCount[idx] > 0) {
charCount[idx]--;
} else {
bool canTransform = false;
for (int j = 0; j < 26; j++) {
if (charCount[j] > 0 && (((j + 1) % 26 + 'a') == c)) {
canTransform = true;
charCount[j]--;
break;
}
}
if (!canTransform) return false;
}
}
return true;
}function canFormSubsequenceByCharFreq(str1, str2) {
const charCount = new Array(26).fill(0);
for (let char of str1) {
charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let char of str2) {
const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
if (charCount[idx] > 0) {
charCount[idx]--;
} else {
let canTransform = false;
for (let j = 0; j < 26; j++) {
if (charCount[j] > 0 && (String.fromCharCode((j + 1) % 26 + 'a'.charCodeAt(0)) === char)) {
canTransform = true;
charCount[j]--;
break;
}
}
if (!canTransform) return false;
}
}
return true;
}#include <stdbool.h>
#include <string.h>
bool canFormSubsequenceByCharFreq(char *str1, char *str2) {
int charCount[26] = {0};
for (int i = 0; str1[i] != '\0'; i++) {
charCount[str1[i] - 'a']++;
}
for (int i = 0; str2[i] != '\0'; i++) {
int currentChar = str2[i] - 'a';
if (charCount[currentChar] > 0) {
charCount[currentChar]--;
} else {
bool canForm = false;
for (int j = 0; j < 26; j++) {
if (charCount[j] > 0 && (((j + 1) % 26 + 'a') == str2[i])) {
charCount[j]--;
canForm = true;
break;
}
}
if (!canForm) return false;
}
}
return true;
}public class Solution {
public bool CanFormSubsequenceByCharFreq(string str1, string str2) {
int[] charCount = new int[26];
foreach (char c in str1) {
charCount[c - 'a']++;
}
foreach (char c in str2) {
int idx = c - 'a';
if (charCount[idx] > 0) {
charCount[idx]--;
} else {
bool canTransform = false;
for (int j = 0; j < 26; j++) {
if (charCount[j] > 0 && (((j + 1) % 26 + 'a') == c)) {
canTransform = true;
charCount[j]--;
break;
}
}
if (!canTransform) return false;
}
}
return true;
}
}Python's solution conducts character transformation checks by maintaining a frequency register for `str1`, testing potential transformations in seeking sub-sequential emergence within `str2`. Prompt checking ceases unsuccessful allocation.
Time Complexity: O(n + m + 26), handling all input and cycling efforts.
Space Complexity: O(1), dependent on a static mechanism.
Approach 3: Two Pointers
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).
function canMakeSubsequence(str1: string, str2: string): boolean {
let i = 0;
const n = str2.length;
for (const c of str1) {
const d = c === 'z' ? 'a' : String.fromCharCode(c.charCodeAt(0) + 1);
if (i < n && (str2[i] === c || str2[i] === d)) {
++i;
}
}
return i === n;
}func canMakeSubsequence(str1 string, str2 string) bool {
i, n := 0, len(str2)
for _, c := range str1 {
d := byte('a')
if c != 'z' {
d = byte(c + 1)
}
if i < n && (str2[i] == byte(c) || str2[i] == d) {
i++
}
}
return i == n
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two Pointer Technique | Time Complexity: O(n + m), iterating through each relevant character once. |
| Approach 2: Character Frequency Analysis | Time Complexity: O(n + m + 26), handling all input and cycling efforts. |
| Two Pointers | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Make String a Subsequence Using Cyclic Increments easy or hard?
The problem is rated Medium because it requires recognizing a greedy subsequence pattern combined with a cyclic character transformation. Once the two-pointer insight is identified, the implementation becomes straightforward.
Make String a Subsequence Using Cyclic Increments Python/Java solution
Most implementations follow the same pattern across languages. Maintain two indices for str1 and str2, compare characters, and check whether the str1 character equals the target or equals the cyclic incremented value. This logic works identically in Python, Java, C++, JavaScript, and C#.
How to solve Make String a Subsequence Using Cyclic Increments in O(n)?
Use two pointers to scan both strings. For each character in str1, check whether it matches the current character in str2 either directly or after applying a cyclic increment. If it matches, move the pointer in str2 forward. Continue until str2 is fully matched or str1 ends.
What is the best approach for Make String a Subsequence Using Cyclic Increments?
The optimal approach is a greedy two-pointer scan. Iterate through str1 while matching characters in str2. A character in str1 can match str2 if it is equal or becomes equal after one cyclic increment (z wraps to a). This runs in O(n) time and O(1) space.
Is Make String a Subsequence Using Cyclic Increments asked at Google/Amazon/Meta?
Problems involving subsequence checks and greedy string transformations commonly appear in interviews at companies like Google, Amazon, and Meta. Variations test knowledge of two pointers, greedy reasoning, and efficient string traversal.
What data structure is used in Make String a Subsequence Using Cyclic Increments?
The solution primarily uses the two-pointer technique on strings. No additional data structures are required beyond basic character comparison and simple arithmetic to compute the cyclic increment.
What is the time complexity of Make String a Subsequence Using Cyclic Increments?
The optimal solution runs in O(n) time where n is the length of str1. Each character is processed once while advancing pointers through the strings. The algorithm uses constant extra memory, so the space complexity is O(1).