Is Subsequence

Difficulty: Easy | Acceptance: 49.00% | Paid: No Topics: Two Pointers, String, Dynamic Programming

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

• Examples
• Constraints
• Two Pointers
• Dynamic Programming
• Binary Search

Examples

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: "a", "b", "c" appear in t in order.

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: "a", "x", "c" don't appear in t in order.

Constraints

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

Two Pointers

Intuition Use two pointers to traverse both strings simultaneously, matching characters from s in t while maintaining order.

Steps

• Initialize two pointers at the start of both strings
• Move through t, advancing the s pointer only when characters match
• Return true if we reach the end of s, false otherwise

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

Complexity

• Time: O(n + m) where n = len(s), m = len(t)
• Space: O(1)
• Notes: Most efficient for single query, simple and intuitive

Dynamic Programming

Intuition Build a 2D table where dp[i][j] indicates if s[0:i] is a subsequence of t[0:j], using previous results to fill current cells.

Steps

• Create a (m+1) x (n+1) DP table initialized to false
• Set dp[0][j] = true for all j (empty string is subsequence of any string)
• Fill table: if characters match, inherit from diagonal; otherwise, inherit from left
• Return dp[m][n]

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        
        for j in range(n + 1):
            dp[0][j] = True
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = dp[i][j - 1]
        
        return dp[m][n]

Complexity

• Time: O(m × n) where m = len(s), n = len(t)
• Space: O(m × n)
• Notes: Useful for understanding the problem structure, but less efficient than two pointers

Binary Search

Intuition Preprocess t to store indices of each character, then use binary search to find valid positions for each character in s.

Steps

• Build a map from character to sorted list of its indices in t
• For each character in s, binary search for the smallest index greater than previous position
• If any character is missing or no valid position exists, return false

from bisect import bisect_left
from collections import defaultdict

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        char_indices = defaultdict(list)
        for idx, char in enumerate(t):
            char_indices[char].append(idx)
        
        prev_idx = -1
        for char in s:
            if char not in char_indices:
                return False
            indices = char_indices[char]
            i = bisect_left(indices, prev_idx + 1)
            if i == len(indices):
                return False
            prev_idx = indices[i]
        
        return True

Complexity

• Time: O(n + m × log(k)) where n = len(t), m = len(s), k = average occurrences per character
• Space: O(n) for storing character indices
• Notes: Optimal for multiple queries against the same t string