Watch 8 video solutions for Subsequence After One Replacement, a medium level problem. This walkthrough by CodeWithMeGuys has 1,545 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings s and t consisting of lowercase English letters.
You may choose at most one index in s and replace the character at that index with any lowercase English letter.
Return true if it is possible to make s a subsequence of t; otherwise, return false.
Example 1:
Input: s = "cat", t = "chat"
Output: true
Explanation:
s[1] from 'a' to 'h'. The resulting string is "cht"."cht" is a subsequence of "chat" because we can match 'c', 'h', and 't' in order.Example 2:
Input: s = "plane", t = "apple"
Output: false
Explanation:
'p', 'l', and 'e' can be matched in t, but the remaining characters cannot be matched while preserving the required order.s, it is impossible to make s a subsequence of t.
Constraints:
1 <= s.length, t.length <= 105s and t consist only of lowercase English letters.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Replacement Check | O(26 * n * m) | O(1) | Small inputs or validating logic during debugging |
| Greedy Two Pointers | O(n + m) | O(1) | General case and interview-expected solution |
| Dynamic Programming | O(n * m) | O(n * m) | Useful when extending to multiple replacements |