Is Subsequence - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Determine if string s is a subsequence of string t, where s's characters appear in t in the same order.
Check if s is empty; if so, return True as an empty string is a subsequence.
If length of s is greater than t, return False as s cannot be a subsequence.
Initialize a pointer j to 0 to track the current position in s.
Iterate through each character in t using index i.
If t[i] equals s[j], increment j; if j reaches the length of s, return True.
After the loop, return False if not all characters of s were found.

Code Solution

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        S = len(s)
        T = len(t)
        if s == '': return True
        if S > T: return False

        j = 0
        for i in range(T):
            if t[i] == s[j]:
                if j == S-1:
                    return True
                j += 1
        
        return False
      # Time: O(T)
      # Space: O(1)

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int sp = 0;
        int tp = 0;

        while (sp < s.length() && tp < t.length()) {
            if (s[sp] == t[tp]) {
                sp++;
            }
            tp++;
        }

        return sp == s.length();        
    }
};

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sp = 0;
        int tp = 0;

        while (sp < s.length() && tp < t.length()) {
            if (s.charAt(sp) == t.charAt(tp)) {
                sp++;
            }
            tp++;
        }

        return sp == s.length();        
    }
}

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let sp = 0;
    let tp = 0;

    while (sp < s.length && tp < t.length) {
        if (s[sp] === t[tp]) {
            sp++;
        }
        tp++;
    }

    return sp === s.length;    
};

Detailed Explanation

What Is the “Is Subsequence” Problem?

The “Is Subsequence” problem is a popular coding question found on platforms like LeetCode. It asks whether a given string s is a subsequence of another string t. A subsequence is a series of characters that appear in the same relative order, but not necessarily contiguously. For example, the string "abc" is a subsequence of "ahbgdc", because the characters a, b, and c appear in the correct order, even though there are other characters in between.

Why This Problem Matters

This problem is commonly used to test your understanding of string manipulation, two-pointer techniques, and greedy algorithms. It also appears in real-world applications, such as validating input sequences, matching patterns in data streams, or building recommendation engines that rely on partial matches.

Step-by-Step Approach

To solve this efficiently, we use a two-pointer technique. Here's how it works:

Initialize a pointer j to 0 to track the current position in s.
Iterate through each character in t using a second pointer.
Each time a character in t matches the current character in s, increment j.
If j reaches the end of s, that means all characters in s were found in order—return true.
If the loop ends before j reaches the end of s, return false.

Example Walkthrough

Let’s consider the example s = "abc" and t = "ahbgdc":

t[0] = 'a' matches s[0] → move j to 1
t[1] = 'h' ≠ s[1] → skip
t[2] = 'b' matches s[1] → move j to 2
t[3] = 'g' ≠ s[2] → skip
t[4] = 'd' ≠ s[2] → skip
t[5] = 'c' matches s[2] → j = 3, end of s

Since all characters in s were matched in order, we return true.

Edge Cases

Here are a few important cases to keep in mind:

If s is an empty string, return true – the empty string is a subsequence of any string.
If t is shorter than s, return false – it’s impossible for s to be a subsequence.

Time and Space Complexity

This algorithm runs in O(n) time, where n is the length of t. We only scan through each character of t once. The space complexity is O(1) since we don’t use any additional data structures beyond a few variables.

Conclusion

The “Is Subsequence” problem is an excellent exercise in understanding how to use two pointers effectively. It combines string processing with a greedy strategy and is useful preparation for more complex problems involving subsequences, string searching, and pattern matching.

Get Personalized Support at AlgoMap Bootcamp 💡