Skip to main content
Talentd

Subsequence After One Replacement - Solution & Explanation

MediumTwo PointersString9 min read
Practice this problem

Problem Statement

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:

  • Replace 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:

  • The characters 'p', 'l', and 'e' can be matched in t, but the remaining characters cannot be matched while preserving the required order.
  • Even after replacing any one character in s, it is impossible to make s a subsequence of t.

 

Constraints:

  • 1 <= s.length, t.length <= 105
  • s and t consist only of lowercase English letters.

Approach Overview

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.

Solution

The problem is equivalent to asking whether we can greedily match s as a subsequence of t while allowing at most one character in s to mismatch, since that character can be replaced with any letter.

We scan s with two pointers i_0 and i_1, and scan t with pointer j:

  • i_0 is the current position in s when matching without using the replacement.
  • i_1 is the current position in s when matching with at most one replacement available.

For each character t[j]:

  1. If s[i_1] = t[j], move i_1 forward by one.
  2. Set i_1 = max(i_1, i_0 + 1) so the replacement position is never before i_0, reserving one character for the replacement.
  3. If s[i_0] = t[j], move i_0 forward by one.
  4. Move j forward by one.

After the scan, if i_1 = |s|, then all characters of s can be matched in order within t using at most one replacement, so return true; otherwise return false.

The time complexity is O(|s| + |t|), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Replacement CheckO(26 * n * m)O(1)Small inputs or validating logic during debugging
Greedy Two PointersO(n + m)O(1)General case and interview-expected solution
Dynamic ProgrammingO(n * m)O(n * m)Useful when extending to multiple replacements

Video Solution

Leetcode 3983 | Subsequence After One Replacement | Weekly contest 509 • CodeWithMeGuys • 1,545 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Subsequence After One Replacement easy or hard?
Subsequence After One Replacement is generally considered a medium-level problem. The core subsequence check is straightforward, but recognizing why a greedy replacement works requires stronger reasoning about ordering constraints.
Subsequence After One Replacement Python/Java solution
Python and Java implementations both follow the same greedy logic using two indices and a boolean flag for the replacement operation. The runtime remains O(n + m) across languages.
How to solve Subsequence After One Replacement in O(n)?
Use two pointers to traverse both strings in order. When characters match, move both pointers. On the first mismatch, consume the allowed replacement and continue. A second mismatch means the subsequence condition cannot be satisfied.
What is the best approach for Subsequence After One Replacement?
The greedy two-pointer approach is the best solution for this problem. It scans both strings once, tracks whether the replacement has been used, and runs in O(n + m) time with O(1) extra space.
Is Subsequence After One Replacement asked at Google/Amazon/Meta?
Subsequence and greedy string matching problems are common in interviews at companies like Google, Amazon, and Meta. Variants involving replacements, edits, or subsequence validation frequently appear in medium-level coding rounds.
What data structure is used in Subsequence After One Replacement?
The optimal solution mainly uses two pointers and simple variables for tracking state. No advanced data structures are required, which keeps the memory usage constant.
What is the time complexity of Subsequence After One Replacement?
The optimal greedy solution runs in O(n + m) time because each pointer moves forward at most once. Space complexity stays O(1) since only counters and flags are stored.

Ready to solve this problem?

Practice Subsequence After One Replacement with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water