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).

Description Hints 4 Solution Video 13:39

2825. Make String a Subsequence Using Cyclic Increments

Medium65.7% acceptance1 company

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 <= 10⁵
1 <= str2.length <= 10⁵
str1 and str2 consist of only lowercase English letters.

Asked at 1 company

Amazon

Topics

String Two Pointers

Hints open one at a time

Hint 1

Consider the indices we will increment separately.

Hint 2

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

Hint 3

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.

Hint 4

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.

13:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution