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.

Description Hints 4 Solution Video 26:31

3983. Subsequence After One Replacement

Medium21.6% acceptance

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 <= 10⁵
s and t consist only of lowercase English letters.

Topics

String Two Pointers

Hints open one at a time

Hint 1

If s.length > t.length, the answer is false.

Hint 2

First check whether s is already a subsequence of t.

Hint 3

For each index i in s, compute the earliest position in t after matching s[0..i-1], and the latest position in t before matching s[i+1..s.length - 1].

Hint 4

Try each index i of s as the character to replace. The characters before i and after i must still be matchable in order inside t, with at least one unused position between them for the replaced character.

26:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def canMakeSubsequence(self, s: str, t: str) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"cat"
"chat"

Input

"plane"
"apple"

Your code is saved on this device.Solution