## Introduction

In this article, we will walk through one of the string-related problems on Leetcode called ‘Is Subsequence’. We will explore various approaches to solve this problem in Python, analyze the time complexity, and understand the underlying concepts involved.

## Problem Statement

The ‘Is Subsequence’ problem can be found on Leetcode with the problem number 392. The problem statement is as follows:

Given two strings `s`

and `t`

, return `True`

if `s`

is a subsequence of `t`

, and `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:

```
Input: s = "abc", t = "ahbgdc"
Output: True
```

## Approach 1: Using Iterators

- Create an iterator for string
`t`

. - Iterate through each character
`ch`

in string`s`

and check if`ch`

is in the remaining part of the iterator. - If all characters of
`s`

are found in the sequence in`t`

, return`True`

, otherwise, return`False`

.

```
def isSubsequence(s, t):
t_iterator = iter(t)
return all(char in t_iterator for char in s)
```

### Time Complexity

The time complexity of this approach is O(n), where n is the length of string `t`

.

## Approach 2: Using Two Pointers

- Initialize two pointers,
`i`

and`j`

, to 0. Pointer`i`

will track the index in string`s`

, and pointer`j`

will track the index in string`t`

. - Iterate through string
`t`

with pointer`j`

. For each character, check if it is equal to the character at index`i`

in string`s`

. - If they are equal, increment
`i`

. If`i`

becomes equal to the length of`s`

, it means all characters are found in sequence, and we return`True`

. - If the loop ends and
`i`

is still less than the length of`s`

, return`False`

.

```
def isSubsequence(s, t):
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)
```

### Time Complexity

The time complexity of this approach is also O(n), where n is the length of string `t`

.

## Approach 3: Using Binary Search (For Multiple Queries)

If you have to answer multiple queries of `s`

with the same `t`

, you can preprocess `t`

and use binary search.

- Create a list for each character in
`t`

storing the indices where the character appears. - For each character in
`s`

, binary search for the smallest index in`t`

that is greater than the index found for the last character. - If such an index doesnâ€™t exist for any character, return
`False`

.

```
import bisect
def isSubsequence(s, t):
# Preprocess t
indices = [[] for _ in range(256)]
for i, ch in enumerate(t):
indices[ord(ch)].append(i)
# Binary search for each character in s
prev_index = -1
for ch in s:
current_indices = indices[ord(ch)]
pos = bisect.bisect_right(current_indices, prev_index)
if pos == len(current_indices):
return False
prev_index = current_indices[pos]
return True
```

### Time Complexity

The time complexity of preprocessing is O(n), and answering each query is O(m * log(n)), where m is the length of `s`

and n is the length of `t`

.

## Conclusion

The ‘Is Subsequence’ problem on Leetcode is a string problem that can be solved using different algorithms, including iterators, two pointers, and binary search (for multiple queries). Understanding these different approaches is not only helpful for solving this specific problem but can also be applied to various other string manipulation problems.