Subsequence After One Replacement - Video Solutions

Problem Overview: You need to determine whether one string can be matched as a subsequence of another after performing at most one character replacement. The challenge is handling the replacement greedily without breaking the relative order constraint required by subsequences.

Approach 1: Brute Force Character Replacement (O(26 * n * m) time, O(1) space)

Try replacing each character position with every possible lowercase letter, then run a standard subsequence check using two pointers. The subsequence validation iterates through both strings and advances pointers whenever characters match. This approach is easy to reason about and useful for validating edge cases during interviews, but it becomes inefficient when the strings grow large because every replacement candidate triggers another full scan.

Approach 2: Greedy Two Pointers (O(n + m) time, O(1) space)

The optimal solution uses a two pointers traversal. Iterate through both strings while tracking whether the single replacement has already been used. When characters match, move both pointers forward. On the first mismatch, consume the replacement and continue matching as if the characters were equal. A second mismatch after using the replacement immediately fails the check. The key insight is that subsequences only depend on order, so a greedy replacement at the earliest mismatch always preserves the maximum remaining search space.

Approach 3: Dynamic Programming Validation (O(n * m) time, O(n * m) space)

A dynamic programming solution stores the longest valid subsequence length while tracking whether a replacement has already been used. Each state represents the best progress for prefixes of the two strings. Matching characters extend the subsequence naturally, while mismatched characters can transition through the single replacement state. This approach is heavier than necessary for the problem constraints, but it generalizes well if the interview extends the problem to multiple replacements or weighted operations.

Recommended for interviews: Interviewers typically expect the greedy greedy two-pointer solution because it achieves linear time with constant extra memory. Showing the brute force approach first demonstrates understanding of the subsequence condition, while deriving the greedy optimization proves you can reduce unnecessary rescans and reason about ordering constraints efficiently.