# Is Subsequence

## June 9, 2020

## Introduction

Given a string s and a string t, check if s is subsequence of t.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits: Special thanks to @pbrother for adding this problem and creating all test cases.

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^4
Both strings consists only of lowercase characters.
```

## Solution

Very simple DP solution

```
func isSubsequence(s string, t string) bool {
n, m := len(s), len(t)
dp := make([][]bool, n+1)
dp[0] = make([]bool, m+1)
for j := 0; j <= m; j++ {
dp[0][j] = true
}
for i := 1; i <= n; i++ {
dp[i] = make([]bool, m+1)
for j := 1; j <= m; j++ {
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[n][m]
}
```

Performance of this solution is:

```
Runtime: 0 ms
Memory Usage: 2.4 MB
```

Let’s do follow up. The bottleneck in 1b requests is memory. There if we decrease using memory and reuse `prev`

and `next`

in each request, we are fine.

```
func isSubsequence(s string, t string) bool {
n, m := len(s), len(t)
prev := make([]bool, m+1)
next := make([]bool, m+1)
for j := 0; j <= m; j++ {
prev[j] = true
}
for i := 1; i <= n; i++ {
next[0] = false
for j := 1; j <= m; j++ {
if s[i-1] == t[j-1] {
next[j] = prev[j-1]
} else {
next[j] = next[j-1]
}
}
prev, next = next, prev
}
return prev[m]
}
```