Is Subsequence - Practice Coding Problems

Is Subsequence - Problem

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. For example, "ace" is a subsequence of "abcde" while "aec" is not.

Input & Output

Example 1 — Basic Subsequence

$ Input: s = "abc", t = "aabbcc"

› Output: true

💡 Note: We can find 'a', then 'b', then 'c' in order within "aabbcc": a(a)b(b)c(c)

Example 2 — Not a Subsequence

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

› Output: false

💡 Note: We find 'a', then find 'h', 'b', 'g', 'd' but no 'x' appears before 'c'

Example 3 — Empty Subsequence

$ Input: s = "", t = "hello"

› Output: true

💡 Note: Empty string is always a subsequence of any string

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s and t

Process

Check if s can be formed by deleting characters from t

Output

Return true if s is a subsequence of t

Key Takeaway

🎯 Key Insight: Use two pointers to scan once - no need to backtrack or try all combinations

Asked in

a Amazon 8 G Google 5 M Microsoft 4 f Facebook 3

The key insight is that we only need to scan each string once using two pointers. The optimal approach uses two pointers moving forward through both strings, matching characters when found. Time: O(t), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(s × t)	O(s × t)	Use recursion with memoization to avoid recomputing subproblems
Recursive with All Combinations	O(2^t)	O(t)	Try all possible ways to pick characters from string t to match s
Two Pointers (Optimal)	O(t)	O(1)	Use two pointers to scan both strings once from left to right

Dynamic Programming with Memoization — Algorithm Steps

Define recursive function with current positions in s and t
Use memoization to cache results for each (i,j) state
Base cases: if i reaches end of s return true, if j reaches end of t return false
Try matching current character or skip it in t

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursive Call

Check if (i,j) state already computed

Cache Miss

Compute result and store in memo table

Cache Hit

Return cached result for repeated states

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_LEN 1001
static int memo[MAX_LEN][MAX_LEN];
static bool memo_set[MAX_LEN][MAX_LEN];

bool helper(const char* s, const char* t, int i, int j, int s_len, int t_len) {
    if (memo_set[i][j]) {
        return memo[i][j];
    }
    
    if (i == s_len) return true;
    if (j == t_len) return false;
    
    bool result = false;
    if (s[i] == t[j]) {
        result = helper(s, t, i + 1, j + 1, s_len, t_len);
    }
    
    if (!result) {
        result = helper(s, t, i, j + 1, s_len, t_len);
    }
    
    memo[i][j] = result;
    memo_set[i][j] = true;
    return result;
}

bool solution(const char* s, const char* t) {
    int s_len = strlen(s);
    int t_len = strlen(t);
    
    // Clear memoization
    memset(memo_set, false, sizeof(memo_set));
    
    return helper(s, t, 0, 0, s_len, t_len);
}

int main() {
    char s[MAX_LEN], t[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    
    // Remove newlines
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    bool result = solution(s, t);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(s × t)

Each (i,j) state computed once, at most s×t states

✓ Linear Growth

Space Complexity

O(s × t)

Memoization table stores results for s×t states plus recursion stack

✓ Linear Space

285.0K Views

Medium Frequency

~15 min Avg. Time

4.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler