Skip to content

3983. Subsequence After One Replacement

Description

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.

Solutions

Solution 1: Two Pointers

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def canMakeSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        i0 = i1 = j = 0

        while i1 < m and j < n:
            if s[i1] == t[j]:
                i1 += 1
            i1 = max(i1, i0 + 1)

            if s[i0] == t[j]:
                i0 += 1

            j += 1

        return i1 == m

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean canMakeSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        int i0 = 0, i1 = 0, j = 0;

        while (i1 < m && j < n) {
            if (s.charAt(i1) == t.charAt(j)) {
                i1++;
            }

            i1 = Math.max(i1, i0 + 1);

            if (s.charAt(i0) == t.charAt(j)) {
                i0++;
            }

            j++;
        }

        return i1 == m;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canMakeSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i0 = 0, i1 = 0, j = 0;

        while (i1 < m && j < n) {
            if (s[i1] == t[j]) {
                i1++;
            }

            i1 = max(i1, i0 + 1);

            if (s[i0] == t[j]) {
                i0++;
            }

            j++;
        }

        return i1 == m;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func canMakeSubsequence(s string, t string) bool {
    m, n := len(s), len(t)
    i0, i1, j := 0, 0, 0

    for i1 < m && j < n {
        if s[i1] == t[j] {
            i1++
        }

        if i1 < i0+1 {
            i1 = i0 + 1
        }

        if s[i0] == t[j] {
            i0++
        }

        j++
    }

    return i1 == m
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function canMakeSubsequence(s: string, t: string): boolean {
    const m = s.length,
        n = t.length;
    let i0 = 0,
        i1 = 0,
        j = 0;

    while (i1 < m && j < n) {
        if (s[i1] === t[j]) {
            i1++;
        }

        i1 = Math.max(i1, i0 + 1);

        if (s[i0] === t[j]) {
            i0++;
        }

        j++;
    }

    return i1 === m;
}

Comments