LeetCode 2825 - Make String a Subsequence Using Cyclic Increments

LeetCode Problem 2825

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us two lowercase strings, str1 and str2. We are allowed to perform at most one global operation on str1. During this operation, we may choose any subset of indices in str1, and increment the character at each chosen index by one alphabetically. The increment is cyclic, meaning 'z' becomes 'a'.

After performing this operation once, or choosing not to perform it at all, we need to determine whether str2 can appear as a subsequence of the resulting str1.

A subsequence does not require characters to be contiguous. The only requirement is that the characters appear in the same relative order.

The important detail is that each character in str1 has only two possible states:

1. Keep the original character.
2. Increment it exactly once cyclically.

For example:

• 'a' can become 'a' or 'b'
• 'c' can become 'c' or 'd'
• 'z' can become 'z' or 'a'

We need to decide whether we can match every character of str2 in order while scanning through str1.

The constraints are large:

• 1 <= str1.length <= 10^5
• 1 <= str2.length <= 10^5

These limits immediately rule out expensive exponential or quadratic solutions. Since both strings can contain one hundred thousand characters, we need a linear or near linear algorithm.

Several edge cases are especially important:

• Characters near the end of the alphabet, especially 'z', because of cyclic wrapping.
• Cases where str2 is longer than str1, which must always return false.
• Situations where a character can only match after incrementing.
• Situations where incrementing would break another match if handled incorrectly.
• Strings where multiple valid matching paths exist.

The problem guarantees that all characters are lowercase English letters, so character arithmetic is straightforward.

Approaches

Brute Force Approach

A brute force solution would try every possible subset of indices in str1 to increment.

If str1 has length n, then there are 2^n possible subsets. For each subset:

1. Create the transformed version of str1.
2. Check whether str2 is a subsequence.
3. Return true if any transformation works.

This approach is correct because it explicitly explores every valid operation configuration. However, it is computationally impossible for the given constraints.

For n = 100000, even enumerating the subsets is infeasible.

Another slightly improved brute force idea would use backtracking while attempting to match str2, deciding for each character whether to increment it or not. Even then, the branching factor still leads to exponential complexity in the worst case.

Key Insight

The crucial observation is that every character in str1 can independently match at most two characters:

• itself
• its cyclic increment

Because subsequence matching only depends on order, we never need to reconsider earlier choices. If a character in str1 can help match the current needed character in str2, we should greedily use it immediately.

This naturally suggests a two pointer approach:

• One pointer scans str1
• Another pointer tracks progress in str2

For each character in str1, we check whether:

• it directly equals the current target character in str2
• or its incremented version equals the target character

If either condition is true, we consume that character from str2 and move the second pointer forward.

Because subsequence problems are inherently order based, greedily matching as early as possible is always optimal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(n)	Tries every possible increment subset
Optimal	O(n + m)	O(1)	Greedy two pointers with character matching

Where:

• n = len(str1)
• m = len(str2)

Algorithm Walkthrough

1. Initialize two pointers:

• i for traversing str1
• j for tracking how many characters of str2 have been matched

2. Iterate through every character in str1.
3. For the current character str1[i], compute:

• its original value
• its cyclic incremented value

4. Compare these against str2[j], the next character we need to match.
5. If either:

• str1[i] == str2[j]
• or incrementing str1[i] once produces str2[j]

then we can use this character to match the current subsequence position. 6. Move j forward to indicate that one more character of str2 has been matched. 7. Continue scanning until either:

• all characters of str2 are matched, or
• str1 is exhausted

8. At the end:

• if j == len(str2), return true
• otherwise return false

Why it works

The algorithm maintains the invariant that str2[:j] is already matched as a subsequence using characters processed so far in str1.

Whenever a character in str1 can match the next required character in str2, greedily taking it is always safe. Using an earlier valid character can never reduce future matching opportunities because subsequences only require relative ordering.

Since every character has only two possible usable forms, original or incremented, checking those two conditions completely captures all valid transformations.

Python Solution

class Solution:
    def canMakeSubsequence(self, str1: str, str2: str) -> bool:
        j = 0
        
        for ch in str1:
            if j == len(str2):
                break
            
            next_char = chr((ord(ch) - ord('a') + 1) % 26 + ord('a'))
            
            if ch == str2[j] or next_char == str2[j]:
                j += 1
        
        return j == len(str2)

The implementation uses a greedy two pointer strategy.

The variable j tracks how many characters from str2 have already been matched.

We iterate through str1 character by character. For each character, we compute its cyclic incremented version using modular arithmetic:

(chr((ord(ch) - ord('a') + 1) % 26 + ord('a')))

This correctly handles wraparound from 'z' to 'a'.

If either the original character or incremented character matches the current target character in str2, we advance j.

Once j reaches the length of str2, we know the entire subsequence has been matched.

The algorithm scans each string at most once, giving linear complexity.

Go Solution

func canMakeSubsequence(str1 string, str2 string) bool {
	j := 0

	for i := 0; i < len(str1); i++ {
		if j == len(str2) {
			break
		}

		current := str1[i]
		nextChar := byte((current-'a'+1)%26 + 'a')

		if current == str2[j] || nextChar == str2[j] {
			j++
		}
	}

	return j == len(str2)
}

The Go implementation follows the same logic as the Python version.

Since Go strings are byte slices for ASCII characters, we can directly work with byte values. Character arithmetic is straightforward because all inputs are lowercase English letters.

The cyclic increment is computed with modular arithmetic exactly as in Python.

No extra memory allocations are needed beyond a few variables, so the space complexity remains constant.

Worked Examples

Example 1

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

We trace the algorithm step by step.

Step	Current char	Incremented	Target char	Match?	j after
1	'a'	'b'	'a'	Yes	1
2	'b'	'c'	'd'	No	1
3	'c'	'd'	'd'	Yes	2

Now j == len(str2).

Result: true

Example 2

Input:
str1 = "zc"
str2 = "ad"

Step	Current char	Incremented	Target char	Match?	j after
1	'z'	'a'	'a'	Yes	1
2	'c'	'd'	'd'	Yes	2

Entire subsequence matched.

Result: true

Example 3

Input:
str1 = "ab"
str2 = "d"

Step	Current char	Incremented	Target char	Match?	j after
1	'a'	'b'	'd'	No	0
2	'b'	'c'	'd'	No	0

No valid match exists.

Result: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each string is scanned at most once
Space	O(1)	Only a few variables are used

The algorithm processes each character in str1 exactly once. The pointer for str2 only moves forward and never resets, so the total work remains linear.

No auxiliary data structures proportional to input size are needed.

Test Cases

sol = Solution()

# Provided examples
assert sol.canMakeSubsequence("abc", "ad") == True  # increment c -> d
assert sol.canMakeSubsequence("zc", "ad") == True   # z -> a and c -> d
assert sol.canMakeSubsequence("ab", "d") == False   # impossible match

# Exact subsequence already exists
assert sol.canMakeSubsequence("abcdef", "ace") == True  # no increments needed

# Single character wraparound
assert sol.canMakeSubsequence("z", "a") == True  # cyclic increment

# Single character impossible
assert sol.canMakeSubsequence("a", "c") == False  # only a or b possible

# str2 longer than str1
assert sol.canMakeSubsequence("abc", "abcd") == False  # insufficient characters

# Multiple increment matches
assert sol.canMakeSubsequence("xyz", "yza") == True  # all incremented

# Greedy matching correctness
assert sol.canMakeSubsequence("abcz", "bd") == True  # a->b and c->d

# Empty style subsequence behavior not allowed by constraints
# but normal matching still works
assert sol.canMakeSubsequence("a", "a") == True  # direct match

# Repeated characters
assert sol.canMakeSubsequence("aaaa", "bbbb") == True  # every a increments to b

# Mixed direct and increment matches
assert sol.canMakeSubsequence("azc", "bad") == True  # a->b, z->a, c->d

# Cannot preserve order
assert sol.canMakeSubsequence("abc", "ca") == False  # subsequence order violated

Test Summary

Test	Why
"abc", "ad"	Basic increment usage
"zc", "ad"	Tests cyclic wraparound
"ab", "d"	Impossible transformation
"abcdef", "ace"	Direct subsequence
"z", "a"	Wraparound edge case
"a", "c"	Single character failure
"abc", "abcd"	str2 longer than str1
"xyz", "yza"	Every character incremented
"abcz", "bd"	Mixed matching strategy
"a", "a"	Minimal valid input
"aaaa", "bbbb"	Repeated increment operations
"azc", "bad"	Combination of direct and cyclic matches
"abc", "ca"	Order preservation requirement

Edge Cases

Cyclic Wraparound from 'z' to 'a'

The most important edge case is the cyclic increment behavior. A naive implementation might increment 'z' to '{' using ASCII arithmetic instead of wrapping back to 'a'.

For example:

str1 = "z"
str2 = "a"

The implementation correctly handles this using modulo arithmetic:

(chr((ord(ch) - ord('a') + 1) % 26 + ord('a')))

This guarantees proper wraparound behavior.

str2 Longer Than str1

If str2 contains more characters than str1, matching is impossible because subsequences cannot reuse characters.

Example:

str1 = "abc"
str2 = "abcd"

The algorithm naturally handles this because the pointer for str2 can never reach the end before str1 is exhausted.

Ordering Constraints

A common mistake is assuming that matching characters alone is sufficient. Subsequence matching requires preserving order.

Example:

str1 = "abc"
str2 = "ca"

Even though both characters exist, 'c' appears after 'a', so the required ordering cannot be achieved.

The two pointer traversal inherently enforces ordering because both pointers only move forward.