Is Subsequence - LeetCode 392 Solution

Problem Overview

#

The Is Subsequence problem from LeetCode asks you to determine whether one string is a subsequence of another.

Problem Statement: Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (not necessarily consecutive) characters without disturbing the relative positions of the remaining characters.

Example:

• Input: s = "abc", t = "ahbgdc"

• Output: true

• Input: s = "axc", t = "ahbgdc"

• Output: false

Solution Approach

#

C# Solution - Two Pointer Approach

#

Use two pointers to traverse both strings simultaneously. For each character in the target string t, check if it matches the current character in the subsequence string s. If it matches, advance the first pointer. Always advance the second pointer. If we successfully match all characters in s, then s is a subsequence of t.

public class Solution {
    public bool IsSubsequence(string s, string t) {
        var sIndex = 0;
        var tIndex = 0; 

        while(sIndex < s.Length && tIndex < t.Length) {
            if(s[sIndex] == t[tIndex]) sIndex++;
            tIndex++;
        }

        return sIndex == s.Length;
    }
}

Time Complexity: O(n) - where n is the length of string t (single pass through t) Space Complexity: O(1) - only constant extra space used for two pointers

Key Insights

#

1. Two Pointer Technique: Maintain pointers for both strings, advancing independently based on character matches
2. Match Characters: Only advance the subsequence pointer when characters match, always advance the target string pointer
3. Order Preservation: Characters of the subsequence must appear in the same order but don’t need to be consecutive in the target string
4. Validation: Check if sIndex == s.Length to confirm all characters in s were found
5. Early Exit: Loop terminates when either string is exhausted
6. Empty Subsequence: An empty string s is always a subsequence of any string t

Related Problems

#

• Longest Common Subsequence
• Longest Increasing Subsequence
• Count Matching Subsequences

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.