Is Subsequence

LeetCode 392: Is Subsequence Solution & Explanation

Problem Overview

TL;DR: Use two pointers moving at different speeds to verify if all characters of the source string appear in the target string in the correct order.

The LeetCode 392 problem asks us to determine if a string s is a subsequence of another string t. A subsequence is formed by deleting zero or more characters from t without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde", but "aec" is not. This is a popular interview question that tests fundamental string manipulation and pointer management skills.

Brute Force Approach for Is Subsequence

A naive or brute force approach might attempt to generate all possible subsequences of the string t and check if string s matches any of them. Alternatively, a naive recursive solution might branch for every character in t, exploring two possibilities: either including the current character in the subsequence or excluding it.

Pseudo-code for Naive Recursion:

function check(s_index, t_index):
    if s_index == length(s): return true
    if t_index == length(t): return false
    
    if s[s_index] == t[t_index]:
        return check(s_index + 1, t_index + 1)
    
    return check(s_index, t_index + 1)

Complexity Analysis: While the recursive logic above mimics the greedy approach, a true brute force that generates all subsequences would have a time complexity of $O(2^M)$, where $M$ is the length of t.

Why it fails: The constraint for t.length is up to $10^4$. An $O(2^M)$ approach would result in a massive number of operations, far exceeding the time limit (Time Limit Exceeded). Even an unoptimized recursive solution without memoization can hit stack overflow limits or excessive overhead for large inputs.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Create two integer pointers, i (representing the slow pointer for s) and j (representing the fast pointer for t), both initialized to 0.
2. Traversal: Enter a loop that continues as long as i is less than the length of s and j is less than the length of t.
3. Comparison and Movement:
   • Compare the character s[i] with t[j].
   • If s[i] == t[j], it means we found the current required character. Increment i (slow pointer) to look for the next character of s.
   • Regardless of whether a match was found, always increment j (fast pointer) to process the next character in t.
4. Termination Condition: The loop breaks when we either find all characters of s or run out of characters in t.
5. Result: Check if i equals the length of s. If it does, all characters were found in order, so return true. Otherwise, return false.

Execution Flow

Let s = "abc" and t = "ahbgdc".

1. Start: i = 0 ('a'), j = 0 ('a').
2. Step 1: Compare s[0] ('a') with t[0] ('a').
   • Match found.
   • Increment i to 1.
   • Increment j to 1.
   • State: i points to 'b', j points to 'h'.
3. Step 2: Compare s[1] ('b') with t[1] ('h').
   • No match.
   • i stays at 1.
   • Increment j to 2.
   • State: i points to 'b', j points to 'b'.
4. Step 3: Compare s[1] ('b') with t[2] ('b').
   • Match found.
   • Increment i to 2.
   • Increment j to 3.
   • State: i points to 'c', j points to 'g'.
5. Step 4: Compare s[2] ('c') with t[3] ('g').
   • No match.
   • Increment j to 4.
6. Step 5: Compare s[2] ('c') with t[4] ('d').
   • No match.
   • Increment j to 5.
7. Step 6: Compare s[2] ('c') with t[5] ('c').
   • Match found.
   • Increment i to 3.
   • Increment j to 6.
8. End: i (3) equals s.length (3). Return true.

Proof of Correctness

The correctness relies on the invariant that if s is a subsequence of t, there exists a set of indices $k_1 < k_2 < ... < k_n$ in t such that $t[k_x] = s[x]$. Our algorithm finds the smallest valid index $k_1$, then the smallest valid index $k_2 > k_1$, and so on.

Suppose the optimal solution uses an index $k'_x$ for $s[x]$ where $k'_x > k_x$ (the index found by our greedy algorithm). Since $k_x < k'_x$, using $k_x$ leaves a strictly larger suffix of t available for matching the remaining characters $s[x+1...]$. Therefore, the greedy choice never eliminates a valid solution if one exists.

Pattern Reuse Notes

The Two Pointers - Fast & Slow pattern is versatile. While LeetCode 392 uses differential speeds for linear matching, the following problems use the relative speed of pointers to detect cycles or find specific nodes:

• LeetCode 141: Linked List Cycle
• LeetCode 202: Happy Number
• LeetCode 287: Find the Duplicate Number

In these problems, the "Fast" pointer typically moves two steps for every one step of the "Slow" pointer, allowing them to meet if a cycle exists. In LeetCode 392, the speed difference is conditional (Slow moves on match, Fast moves always), but the principle of managing two independent traversal rates remains the same.

Reference Implementation

C++ Solution for LeetCode 392

1class Solution {
2public:
3    bool isSubsequence(string s, string t) {
4        int i = 0; // Pointer for s (Slow)
5        int j = 0; // Pointer for t (Fast)
6        
7        while (i < s.length() && j < t.length()) {
8            if (s[i] == t[j]) {
9                i++; // Move slow pointer only on match
10            }
11            j++; // Move fast pointer always
12        }
13        
14        return i == s.length();
15    }
16};

Java Solution for LeetCode 392

1class Solution {
2    public boolean isSubsequence(String s, String t) {
3        int i = 0; // Pointer for s (Slow)
4        int j = 0; // Pointer for t (Fast)
5        
6        // Iterate while both pointers are within bounds
7        while (i < s.length() && j < t.length()) {
8            if (s.charAt(i) == t.charAt(j)) {
9                i++;
10            }
11            j++;
12        }
13        
14        return i == s.length();
15    }
16}

Python Solution for LeetCode 392

1class Solution:
2    def isSubsequence(self, s: str, t: str) -> bool:
3        i, j = 0, 0
4        n, m = len(s), len(t)
5        
6        while i < n and j < m:
7            if s[i] == t[j]:
8                i += 1
9            j += 1
10            
11        return i == n