#2825

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Make String a Subsequence Using Cyclic Increments

Determine if str2 can be made a subsequence of str1 by incrementing characters cyclically using at most one operation.

Problem Statement

Given two strings str1 and str2, you need to determine if it is possible to make str2 a subsequence of str1 by performing at most one cyclic increment operation on str1. In the operation, you select a set of indices from str1, and for each index i, increment str1[i] to the next character cyclically. For example, 'a' becomes 'b', 'b' becomes 'c', and so on, with 'z' wrapping around to 'a'.

The task is to return true if str2 can be made a subsequence of str1 with at most one operation, otherwise return false. The input strings consist only of lowercase English letters, and the lengths of str1 and str2 are constrained to 1 <= str1.length, str2.length <= 10^5.

Examples

Example 1

Input: str1 = "abc", str2 = "ad"

Output: true

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

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

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

Solution Approach

Two-pointer scanning

Use a two-pointer approach to traverse both str1 and str2. The idea is to try to match characters of str2 with str1, checking if any cyclic increments are necessary. This approach ensures that we scan both strings in linear time, and can efficiently track which characters of str1 need to be incremented.

Invariant tracking

Maintain an invariant where the characters of str2 must match str1, allowing for cyclic increments to bring str1 characters into alignment with str2. This invariant helps identify whether str2 can be formed in a single pass by incrementing characters in str1.

Increment condition

As we progress through str1 and str2, check if each character in str1 can be incremented to match the corresponding character in str2. If a character in str1 is behind the required character in str2, perform a cyclic increment and continue checking. This operation should only be applied once.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of this solution is O(n), where n is the length of str1, as we only need to make a single pass through both str1 and str2. The space complexity is O(1) since no additional data structures are required beyond the two pointers for traversal.

What Interviewers Usually Probe

Look for understanding of two-pointer techniques and cyclic operations.
Check if the candidate can efficiently match characters using one operation.
Evaluate if they understand the invariant tracking to align the two strings.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the cyclic increment operation and assuming non-cyclic transformations are sufficient.
Attempting to apply more than one operation when the problem only allows a single increment.
Failing to maintain the invariant correctly, which could lead to an incorrect result.

Follow-up variants

What if str1 is already a subsequence of str2?
What if the cyclic increment must occur multiple times for different characters?
How does the solution change if we allow more than one operation?

FAQ

What is the main technique for solving the "Make String a Subsequence Using Cyclic Increments" problem?

The primary technique is using two-pointer scanning with invariant tracking to match characters of str2 to str1, applying cyclic increments when needed.

How do you apply cyclic increments to the characters in str1?

Cyclic increments involve selecting indices of str1 and changing each character to the next one in the alphabet, where 'z' wraps around to 'a'.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of str1, since we perform a single pass over both strings.

Can this problem be solved using dynamic programming?

While dynamic programming is not necessary for this problem, two-pointer scanning with careful tracking of increments is the most efficient solution.

What happens if str1 and str2 are already subsequences?

If str1 already contains str2 as a subsequence, the function should return true without any operations, as no increment is required.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        i = 0
        for c in str1:
            d = "a" if c == "z" else chr(ord(c) + 1)
            if i < len(str2) and str2[i] in (c, d):
                i += 1
        return i == len(str2)

Continue Practicing

#2911 minimum changes to make k semi palindromes #2938 separate black and white balls #2697 lexicographically smallest palindrome