LeetCodee

392. Is Subsequence

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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 (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).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10⁴
  • s and t consist only of lowercase English letters.

Follow up:

Suppose there are lots of incoming s, say s₁, s₂, ..., sₖ where k >= 10⁹, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Solution

Python Solution

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # Two-pointer approach
        i = j = 0
        
        # Iterate through both strings
        while i < len(s) and j < len(t):
            # If characters match, move s pointer
            if s[i] == t[j]:
                i += 1
            # Always move t pointer
            j += 1
        
        # Return true if we found all characters of s
        return i == len(s)

Time Complexity: O(n)

Where n is the length of string t. We traverse t at most once.

Space Complexity: O(1)

We only use two pointers regardless of input size.

Java Solution

class Solution {
    public boolean isSubsequence(String s, String t) {
        // Two-pointer approach
        int i = 0, j = 0;
        
        // Iterate through both strings
        while (i < s.length() && j < t.length()) {
            // If characters match, move s pointer
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            // Always move t pointer
            j++;
        }
        
        // Return true if we found all characters of s
        return i == s.length();
    }
}

Time Complexity: O(n)

Where n is the length of string t. We traverse t at most once.

Space Complexity: O(1)

We only use two pointers regardless of input size.

C++ Solution

class Solution {
public:
    bool isSubsequence(string s, string t) {
        // Two-pointer approach
        int i = 0, j = 0;
        
        // Iterate through both strings
        while (i < s.length() && j < t.length()) {
            // If characters match, move s pointer
            if (s[i] == t[j]) {
                i++;
            }
            // Always move t pointer
            j++;
        }
        
        // Return true if we found all characters of s
        return i == s.length();
    }
};

Time Complexity: O(n)

Where n is the length of string t. We traverse t at most once.

Space Complexity: O(1)

We only use two pointers regardless of input size.

JavaScript Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    // Two-pointer approach
    let i = 0, j = 0;
    
    // Iterate through both strings
    while (i < s.length && j < t.length) {
        // If characters match, move s pointer
        if (s[i] === t[j]) {
            i++;
        }
        // Always move t pointer
        j++;
    }
    
    // Return true if we found all characters of s
    return i === s.length;
};

Time Complexity: O(n)

Where n is the length of string t. We traverse t at most once.

Space Complexity: O(1)

We only use two pointers regardless of input size.

C# Solution

public class Solution {
    public bool IsSubsequence(string s, string t) {
        // Two-pointer approach
        int i = 0, j = 0;
        
        // Iterate through both strings
        while (i < s.Length && j < t.Length) {
            // If characters match, move s pointer
            if (s[i] == t[j]) {
                i++;
            }
            // Always move t pointer
            j++;
        }
        
        // Return true if we found all characters of s
        return i == s.Length;
    }
}

Time Complexity: O(n)

Where n is the length of string t. We traverse t at most once.

Space Complexity: O(1)

We only use two pointers regardless of input size.

Follow-up Solution

For the follow-up question where we need to check multiple strings against t, we can preprocess t to create a dictionary of character positions: 

class Solution:
    def __init__(self):
        self.char_indices = {}
    
    def preprocess(self, t: str):
        # Create dictionary of character positions
        self.char_indices = {}
        for i, char in enumerate(t):
            if char not in self.char_indices:
                self.char_indices[char] = []
            self.char_indices[char].append(i)
    
    def isSubsequence(self, s: str, t: str) -> bool:
        # Preprocess t if not already done
        if not self.char_indices:
            self.preprocess(t)
        
        # Current position in t
        curr_pos = -1
        
        # Check each character in s
        for char in s:
            # If character not in t, return false
            if char not in self.char_indices:
                return False
            
            # Find next position of char after curr_pos
            positions = self.char_indices[char]
            pos = bisect_right(positions, curr_pos)
            
            # If no valid position found, return false
            if pos >= len(positions):
                return False
            
            # Update current position
            curr_pos = positions[pos]
        
        return True

Time Complexity:

  • Preprocessing: O(n) where n is the length of t
  • Each query: O(m log n) where m is the length of s

Space Complexity: O(n)

For storing the character positions of t.

Approach Explanation

The solution uses a two-pointer approach for the basic problem:

  1. Key Insights:
    • Order matters
    • Two-pointer technique
    • Linear traversal
    • Early termination
  2. Algorithm Steps:
    • Initialize pointers
    • Compare characters
    • Move pointers
    • Check completion

Implementation Details:

  • Pointer management
  • Character comparison
  • Boundary checks
  • Result validation

Optimization Insights:

  • No extra space
  • Single pass
  • Early termination
  • Efficient checks

Edge Cases:

  • Empty strings
  • Single character
  • No match
  • Complete match