No results found for the specified position. Determine if str1 is a subsequence of str2. Javascript Beginner Level Implementation Mock Interview

MockQuestions

Javascript Beginner Level Implementation Mock Interview

Question 3 of 11 for our Javascript Beginner Level Implementation Mock Interview

Get More Information About Our Javascript Beginner Level Implementation Interview Questions

Question 3 of 11

Determine if str1 is a subsequence of str2.

You are given two strings str1 and str2. Your task is to find if str1 is a subsequence of str2.
A subsequence of a string is a string that is created from the original by deleting zero or more characters with the order of remaining characters the same as the original string.

So if the original string is “abcde”, the possible subsequences are-

“abcde”:- deleting no zero characters.
“abde”:- deleting “c”
“bde”:- deleting “a” and “c”

but these are not valid subsequences-

“aeb”:- the relative order is not the same
“cbz”:- contains another character “z” which is not in the original string

/* Example */

str1 = “abc”, st2 = “ahbgdc”
expected output- true

str1 = “axc”, st2 = “ahbgdc”
expected output- false

Solution:

We will iterate over each character of str1. We will find the index of each character of str1 in str2 starting from the index of the last character in str1. If the found index is -1, we return false, because it does not exist in str2. Otherwise, we continue to the next character of str1. For example-
str1 = “abc”, st2 = “ahbgdc”
start with the first character of str1 => “a”
=> index of “a” in str2 = 0
=> which is not -1
=> continue with next character
=> next character of str1 => “b”
=> index of “b” in str2 after index 0 (index of last character “a”) = 2
=> which is not -1
=> continue with next character
=> index of “c” in str2 after index 2 (index of last character “b”) = 5
=> which is not -1
=> all characters of str1 found in str2 with correct positions
=> return true

Another example-
str1 = “agh”, st2 = “ahbgdc
start with the first character of str1 => “a”
=> index of “a” in str2 = 0
=> which is not -1
=> continue with next character
=> next character of str1 => “g”
=> index of “g” in str2 after index 0 (index of last character “a”) = 3
=> which is not -1
=> continue with next character
=> index of “h” in str2 after index 3 (index of last character “g”) = -1
=> which is -1
=> return false
One thing to note here is that “h” did exist in str2, but it was before the index “g”, and we wanted it after the index “g” which is not the case. So we return -1.
We will use String.prototype.indexOf function to find the index of the character in str2. The function takes two arguments-

1) searchValue:- the string/character whose index we want to find
2) fromIndex (optional):- the index at which we want to start the search (default is 0)

/**
 * @param {string} str1
 * @param {string} str2
 * @return {boolean}
 */
function isSubsequence(str1, str2) {
    let lastIndex = -1
    
    // iterate over each character of str1
    for (const char of str1) {
        // find index of char in str2 starting from
        // index of last character
        lastIndex = str2.indexOf(char, lastIndex + 1)
 
        if (lastIndex === -1) return false
    }
    
    return true
}

m = length of string str1
n = length of string str2
Time complexity- O(m + n)
Space complexity- O(1)

Written by on May 4th, 2021

Next Question

How to Answer: Determine if str1 is a subsequence of str2.

Advice and answer examples written specifically for a Javascript Beginner Level Implementation job interview.

  • 3. Determine if str1 is a subsequence of str2.

      You are given two strings str1 and str2. Your task is to find if str1 is a subsequence of str2.
      A subsequence of a string is a string that is created from the original by deleting zero or more characters with the order of remaining characters the same as the original string.

      So if the original string is “abcde”, the possible subsequences are-

      “abcde”:- deleting no zero characters.
      “abde”:- deleting “c”
      “bde”:- deleting “a” and “c”

      but these are not valid subsequences-

      “aeb”:- the relative order is not the same
      “cbz”:- contains another character “z” which is not in the original string

      /* Example */

str1 = “abc”, st2 = “ahbgdc”
expected output- true

str1 = “axc”, st2 = “ahbgdc”
expected output- false

      Solution:

      We will iterate over each character of str1. We will find the index of each character of str1 in str2 starting from the index of the last character in str1. If the found index is -1, we return false, because it does not exist in str2. Otherwise, we continue to the next character of str1. For example-
      str1 = “abc”, st2 = “ahbgdc”
      start with the first character of str1 => “a”
      => index of “a” in str2 = 0
      => which is not -1
      => continue with next character
      => next character of str1 => “b”
      => index of “b” in str2 after index 0 (index of last character “a”) = 2
      => which is not -1
      => continue with next character
      => index of “c” in str2 after index 2 (index of last character “b”) = 5
      => which is not -1
      => all characters of str1 found in str2 with correct positions
      => return true

      Another example-
      str1 = “agh”, st2 = “ahbgdc
      start with the first character of str1 => “a”
      => index of “a” in str2 = 0
      => which is not -1
      => continue with next character
      => next character of str1 => “g”
      => index of “g” in str2 after index 0 (index of last character “a”) = 3
      => which is not -1
      => continue with next character
      => index of “h” in str2 after index 3 (index of last character “g”) = -1
      => which is -1
      => return false
      One thing to note here is that “h” did exist in str2, but it was before the index “g”, and we wanted it after the index “g” which is not the case. So we return -1.
      We will use String.prototype.indexOf function to find the index of the character in str2. The function takes two arguments-

      1) searchValue:- the string/character whose index we want to find
      2) fromIndex (optional):- the index at which we want to start the search (default is 0)

      /**
 * @param {string} str1
 * @param {string} str2
 * @return {boolean}
 */
function isSubsequence(str1, str2) {
    let lastIndex = -1
    
    // iterate over each character of str1
    for (const char of str1) {
        // find index of char in str2 starting from
        // index of last character
        lastIndex = str2.indexOf(char, lastIndex + 1)
 
        if (lastIndex === -1) return false
    }
    
    return true
}

      m = length of string str1
      n = length of string str2
      Time complexity- O(m + n)
      Space complexity- O(1)

      Written by S. Kumar on June 27th, 2021

    • Next Question