Is Subsequence

Leetcode Problem 392: Is Subsequence

Problem Summary

Given two strings s and t, determine whether s is a subsequence of t.

A string is a subsequence of another if it can be derived by removing some characters (possibly zero) from the original — without changing the relative order of the remaining characters.

For example:

• "ace" is a subsequence of "abcde" (remove 'b' and 'd')
• "aec" is not a subsequence of "abcde" (it would require reordering characters)

Return true if s is a subsequence of t, or false otherwise.

• The length of s is between 0 and 100 characters (can be empty).
• The length of t is between 0 and 10,000 characters (can be empty).
• Both strings consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Techniques

• Two Pointers
• String
• Dynamic Programming

Solution

function isSubsequence(s: string, t: string): boolean {
    let sPosition = 0

    for (let tPosition = 0; tPosition < t.length; tPosition++) {
        let currentCharS = s.charAt(sPosition)
        let currentCharT = t.charAt(tPosition)

        if (currentCharS === currentCharT) {
            sPosition++
        }
    }

    return sPosition === s.length
}

console.log(isSubsequence("axc", "ahbgdc"))
console.log(isSubsequence("abc", "ahbgdc"))