Welcome to Subscribe On Youtube

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

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions