Is Subsequence

easy string two pointers

Problem

Given two strings s and t, check if s is a subsequence of t. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Inputs = "ace", t = "abcde"

Outputtrue

a, c, e appear at indices 0, 2, 4 in t.

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and ch == s[i]:
            i += 1
    return i == len(s)

function isSubsequence(s, t) {
  let i = 0;
  for (let j = 0; j < t.length && i < s.length; j++) {
    if (t[j] === s[i]) i++;
  }
  return i === s.length;
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        for (int j = 0; j < t.length() && i < s.length(); j++) {
            if (t.charAt(j) == s.charAt(i)) i++;
        }
        return i == s.length();
    }
}

bool isSubsequence(string s, string t) {
    int i = 0;
    for (int j = 0; j < (int)t.size() && i < (int)s.size(); j++) {
        if (t[j] == s[i]) i++;
    }
    return i == (int)s.size();
}

Explanation

We need to confirm that every letter of s shows up inside t in the same order (gaps are allowed). The neat way to do this is a single sweep through t while tracking how much of s we have matched so far.

Keep a pointer i into s, starting at 0. Walk through t one character at a time. Whenever the current character of t equals s[i], that letter is matched, so we advance i. If it does not match, we simply move on in t and leave i where it is.

At the end, if i has reached len(s) it means every character of s was matched in order, so the answer is true. Otherwise some letter was never found and the answer is false.

Example: s = "ace", t = "abcde". We match a at index 0, skip b, match c at index 2, skip d, match e at index 4. All three matched, so true.

Because we only walk t once and never go backwards, this is a fast O(|t|) scan using one counter.

Time: O(|t|) Space: O(1)