# Is Subsequence
**Difficulty:** EASY
[External](https://leetcode.com/problems/is-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/is-subsequence
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Tekion](https://scaleengineer.com/companies/tekion), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Pinterest](https://scaleengineer.com/companies/pinterest), [Electronic Arts](https://scaleengineer.com/companies/electronic-arts)
---
## 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. (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 <= 104`
* `s` and `t` consist only of lowercase English letters.

**Follow up:** Suppose there are lots of incoming `s`, say `s1, s2, ..., sk` where `k >= 109`, and you want to check one by one to see if `t` has its subsequence. In this scenario, how would you change your code?

# Approaches
## Dynamic Programming
This approach uses a 2D dynamic programming table to solve the problem. We define `dp[i][j]` as a boolean indicating if the first `i` characters of `s` form a subsequence of the first `j` characters of `t`. The table is filled based on a recurrence relation.
**Time:** O(M * N), where M is the length of `s` and N is the length of `t`. We need to fill the entire M x N DP table. · **Space:** O(M * N) for the DP table, where M and N are the lengths of s and t. This can be optimized to O(N) since each row only depends on the previous row.
**Pros:** A standard DP approach that is easy to understand for those familiar with dynamic programming.; Can be adapted to solve similar string problems.
**Cons:** Inefficient in both time and space compared to other solutions.; Not suitable for large strings due to high memory usage.
### Explanation
We create a DP table `dp` of size `(s.length() + 1) x (t.length() + 1)`. `dp[i][j]` will be `true` if `s.substring(0, i)` is a subsequence of `t.substring(0, j)`. The base case is that an empty string is a subsequence of any string, so the first row of the DP table is set to `true`. For the recurrence relation, if the characters `s.charAt(i-1)` and `t.charAt(j-1)` match, we need to check if the preceding substrings also formed a subsequence (`dp[i-1][j-1]`). If they don't match, we effectively ignore `t.charAt(j-1)` and check if `s.substring(0, i)` is a subsequence of `t.substring(0, j-1)` (`dp[i][j-1]`). The final answer is found in `dp[s.length()][t.length()]`.

```java
public boolean isSubsequence(String s, String t) {
    int m = s.length();
    int n = t.length();

    if (m == 0) {
        return true;
    }

    boolean[][] dp = new boolean[m + 1][n + 1];

    for (int j = 0; j <= n; j++) {
        dp[0][j] = true;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    return dp[m][n];
}
```
### Algorithm
*   Let `m = s.length()` and `n = t.length()`.
*   Create a boolean DP table `dp[m+1][n+1]`.
*   Initialize `dp[0][j] = true` for all `j` from 0 to `n`.
*   Iterate `i` from 1 to `m`:
    *   Iterate `j` from 1 to `n`:
        *   If `s.charAt(i-1) == t.charAt(j-1)`: `dp[i][j] = dp[i-1][j-1]`.
        *   Else: `dp[i][j] = dp[i][j-1]`.
*   Return `dp[m][n]`.

## Two Pointers
This is a greedy and efficient approach that uses two pointers to iterate through the strings `s` and `t`. One pointer tracks the current character to be found in `s`, and the other scans `t` to find that character.
**Time:** O(N), where N is the length of `t`. We iterate through `t` at most once. · **Space:** O(1), as we only use a constant amount of extra space for the pointers.
**Pros:** Very efficient in both time and space.; Simple and intuitive to implement.
**Cons:** For the follow-up scenario with many `s` queries on the same `t`, this approach re-scans `t` every time, which is suboptimal.
### Explanation
We use two pointers, `i` for string `s` and `j` for string `t`. We iterate through `t` with pointer `j`. Whenever we find a character `t.charAt(j)` that matches the character `s.charAt(i)`, we advance the pointer `i` to look for the next character in `s`. We always advance the pointer `j` to scan through `t`. If we have advanced `i` to be equal to the length of `s`, it means all characters of `s` have been found in `t` in the correct order.

```java
public boolean isSubsequence(String s, String t) {
    int i = 0; // pointer for s
    int j = 0; // pointer for t
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) {
            i++;
        }
        j++;
    }
    return i == s.length();
}
```
### Algorithm
*   Initialize two pointers, `i = 0` for `s` and `j = 0` for `t`.
*   Loop while `i < s.length()` and `j < t.length()`:
    *   If `s.charAt(i) == t.charAt(j)`, increment `i`.
    *   Always increment `j`.
*   After the loop, if `i == s.length()`, return `true`. Otherwise, return `false`.

## Optimized Search with Pre-computation (Follow-up)
This approach is designed for the follow-up scenario where we check many `s` strings against a single `t`. It involves pre-processing `t` to map each character to a list of its indices. Then, for each `s`, we can efficiently find the required characters using binary search.
**Time:** O(N + K * M * log(N)), where N=|t|, M=|s|, and K is the number of queries. O(N) for one-time pre-computation. Each query takes O(M * log(N)). · **Space:** O(N), where N is the length of `t`. This is for storing the character indices map. The total number of indices stored across all lists is N.
**Pros:** Highly efficient for the scenario with many queries on a fixed `t`.; The expensive pre-computation is done only once.
**Cons:** Higher overhead for a single query compared to the two-pointer approach.; Uses more memory to store the index map.
### Explanation
This method is ideal for the follow-up problem. First, we pre-process `t` by creating a hash map where keys are characters and values are sorted lists of their indices in `t`. This takes O(|t|) time. Then, to check if a string `s` is a subsequence, we iterate through `s`. For each character, we use binary search on its corresponding index list to find the next available occurrence in `t` (i.e., an index greater than the index of the previous match). If we find a valid index for every character in `s`, it is a subsequence.

```java
// This implementation is for the follow-up scenario.
// For a single call, the two-pointer approach is better.
public boolean isSubsequence(String s, String t) {
    // Pre-computation part
    Map<Character, List<Integer>> charIndices = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        charIndices.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
    }

    // Query part
    int prevMatchIndex = -1;
    for (char c : s.toCharArray()) {
        List<Integer> indices = charIndices.get(c);
        if (indices == null) {
            return false;
        }
        
        int nextMatchIndex = findNextIndex(indices, prevMatchIndex);
        
        if (nextMatchIndex == -1) {
            return false;
        }
        prevMatchIndex = nextMatchIndex;
    }
    return true;
}

// Helper function to find the smallest index > prevMatchIndex
private int findNextIndex(List<Integer> indices, int prevMatchIndex) {
    int left = 0;
    int right = indices.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (indices.get(mid) > prevMatchIndex) {
            result = indices.get(mid);
            right = mid - 1; // Try to find an even smaller index
        } else {
            left = mid + 1;
        }
    }
    return result;
}
```
### Algorithm
*   **Pre-computation:**
    *   Create a map `charIndices` where keys are characters and values are lists of their indices in `t`.
    *   Iterate through `t` and populate this map.
*   **Query for `s`:**
    *   Initialize `last_match_index = -1`.
    *   For each character `c` in `s`:
        *   Get the list of indices for `c` from `charIndices`. If not found, return `false`.
        *   Binary search this list to find the smallest index `idx` such that `idx > last_match_index`.
        *   If no such index is found, return `false`.
        *   Update `last_match_index = idx`.
    *   If the loop completes, return `true`.

# Solutions
### Python

```python
''' >>> a=[1,2,3,1,2,3,1,2,3] >>> bisect.bisect_left(a, 2) 1 >>> bisect.bisect_right(a, 2) 8 ''' class Solution : def isSubsequence ( self , s : str , t : str ) -> bool : i , j , m , n = 0 , 0 , len ( s ), len ( t ) while i < m and j < n : if s [ i ] == t [ j ]: i += 1 j += 1 return i == m # follow up class Solution : def isSubsequence ( self , s : str , t : str ) -> bool : # pre-processing step index = defaultdict ( list ) for i , c in enumerate ( t ): index [ c ]. append ( i ) # iterate through each incoming string s j = 0 for c in s : if c not in index : return False pos_list = index [ c ] pos = bisect_left ( pos_list , j ) if pos == len ( pos_list ): return False j = pos_list [ pos ] + 1 return True
```

### CSharp

```csharp
public class Solution {
    public bool IsSubsequence(string s, string t) {
        int m = s.Length, n = t.Length;
        int i = 0, j = 0;
        for (; i < m && j < n; ++j) {
            if (s[i] == t[j]) {
                ++i;
            }
        }
        return i == m;
    }
}
```

### Java

```java
import java.util.ArrayList ; import java.util.HashMap ; import java.util.List ; import java.util.Map ; public class Is_Subsequence { class Solution { public boolean isSubsequence ( String s , String t ) { if ( s == null || s . length () == 0 ) { return true ; } int i = 0 ; for ( int j = 0 ; j < t . length (); j ++) { if ( s . charAt ( i ) == t . charAt ( j )) { i ++; if ( i == s . length ()) { // last char is matched return true ; } } } return false ; } } class Solution_followup { public boolean isSubsequence ( String s , String t ) { // step 1: save all the index for the t Map < Character , List < Integer >> map = new HashMap <>(); for ( int i = 0 ; i < t . length (); i ++) { char c = t . charAt ( i ); if (! map . containsKey ( c )) { List < Integer > pos = new ArrayList <>(); pos . add ( i ); map . put ( c , pos ); } else { List < Integer > pos = map . get ( c ); pos . add ( i ); // map.put(c, pos); } } // step 2: for each char in s, find the first index int prevIndex = - 1 ; for ( int i = 0 ; i < s . length (); i ++) { char c = s . charAt ( i ); List < Integer > pos = map . get ( c ); if ( pos == null || pos . size () == 0 ) { return false ; } int currentIndex = getNextIndexGreaterThanTarget ( pos , prevIndex ); if ( currentIndex == - 1 ) { return false ; } prevIndex = currentIndex ; } return true ; } // find next number greater than target // if not found, return -1 private int getNextIndexGreaterThanTarget ( List < Integer > pos , int targetIndex ) { int lo = 0 ; int hi = pos . size () - 1 ; while ( lo + 1 <= hi ) { int mid = lo + ( hi - lo ) / 2 ; if ( pos . get ( mid ) == targetIndex ) { lo = mid + 1 ; } else if ( pos . get ( mid ) > targetIndex ) { hi = mid ; } else if ( pos . get ( mid ) < targetIndex ) { lo = mid + 1 ; } } if ( pos . get ( lo ) > targetIndex ) { return pos . get ( lo ); } if ( pos . get ( hi ) > targetIndex ) { return pos . get ( hi ); } return - 1 ; } } } ////// class Solution { public boolean isSubsequence ( String s , String t ) { int m = s . length (), n = t . length (); int i = 0 , j = 0 ; while ( i < m && j < n ) { if ( s . charAt ( i ) == t . charAt ( j )) { ++ i ; } ++ j ; } return i == m ; } }
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/is-subsequence/ // Time: O(M + N) // Space: O(1) class Solution { public: bool isSubsequence ( string s , string t ) { int i = 0 , j = 0 , M = s . size (), N = t . size (); for (; i < M && j < N ; ++ j ) { if ( s [ i ] == t [ j ]) ++ i ; } return i == M ; } };
```