Leetcode – Is Subsequence Solution in Python

Spread the love

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

  1. Create an iterator for string t.
  2. Iterate through each character ch in string s and check if ch is in the remaining part of the iterator.
  3. 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

  1. 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.
  2. Iterate through string t with pointer j. For each character, check if it is equal to the character at index i in string s.
  3. 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.
  4. 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.

  1. Create a list for each character in t storing the indices where the character appears.
  2. For each character in s, binary search for the smallest index in t that is greater than the index found for the last character.
  3. 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.

Leave a Reply