How To Check if One String is a Subsequence of Another?

by

? Companies that asked this problem: Accolite, Tesco, Google

Problem Formulation

Description

Given two strings str1 and str2, check if str1 is a subsequence of str2.

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).

constraints:

  • 0 <= str1.length <= 100
  • 0 <= str2.length <= 104
  • str1 and str2 consist only of lowercase English letters.

Example

Input: str1 = "abc", str2 = "ahbgdc"
Output: True

Input: str1 = "axc", str2 = "ahbgdc"
Output: False

Border Cases

  • If str1 and str2 are both empty, then Output → TRUE, as empty string a subsequence of another empty string.
  • If str1 → empty and str2 → not empty, then Output → TRUE, as empty string is also a subsequence of any given string.
  • If str1 → not empty and str2 → empty, then Output → FALSE, as non-empty string cannot be subsequence of empty string.
Input: str1 = "", str2 = ""
Output: True

Input: str1 = "", str2 = "ahbgdc"
Output: True

Input: str1 = "abc", str2 = ""
Output: False

Proposed Solution Overview

Traverse through each character in the given strings. There are two cases when you do so:

  1. The current characters of both strings are equal. So, move on to the next next index/character of str1 and str2.
  2. Current characters of both strings are not equal. So, move on to the next index/character of str2. However the index of str1 remains fixed in this case since the matching character was not found.

The above process is repeated until on of the following criteria’s are satisfied:

  1. All characters of str1 are found to be present in str2. The length of str1 and the current value of index_str1 will be equal in this case. This denotes that we successfully found the subsequence within the given string. In other words, str1 is a subsequence of str2.
  2. All characters of str2 have been traversed. This means that either the last character of str1 and str2 are equal or str2 is not a subsequence of str1.

Diagrammatic representation:

Solution

def isSubSequence(str1, str2):
    len_str1 = len(str1)
    len_str2 = len(str2)
    index_str1 = 0  
    index_str2 = 0  
    # Traverse both str1 and str2
    while index_str1 < len_str1 and index_str2 < len_str2:
        # Compare current character of str2 with str1
        if str1[index_str1] == str2[index_str2]:
            # If matched, then move to next character in str1
            index_str1 = index_str1 + 1
        index_str2 = index_str2 + 1
    return index_str1 == len_str1


val_1 = 'abc'
val_2 = 'ahbgdc'
print(isSubSequence(val_1, val_2))

Output:

True

Code Explanation:

  • len_str1 and len_str2 store the length of str1 and str2 respectively.
  • index_str1 and index_str2 are used to store the indices of each character of str1 and str2 respectively.
  • The while loop is used to traverse through the strings until a match is found or all the indices of str2 have been traversed in case of no match.
    • The if statement compares the current character of str1 and str2.
      • In case a match is found, the index of the next character in str1 is taken into account.
    • The value of index_str1 is incremented at every iteration to traverse through all the letters available in str1 until the subsequence is found.
  • Finally, if the subsequence was found the value stored by index_str1 will be equal to the length of str1.

Dry Run:

The following table illustrates the operation at each iteration within the while loop until the match is found.

? Video Solution