Lesson

8.16Check Subsequence

Problem Statement

Determine if one string is a subsequence of another (order matters, but not consecutiveness).

Example Inputs

Input: "abc", "ahbgdc"
- Output: true
Input: "axc", "ahbgdc"
- Output: false
Input: "ace", "abcde"
- Output: true
Input: "aec", "abcde"
- Output: false

JavaScript Method - Using Only String Methods

Approach

To check if a string is a subsequence of another, we can iterate through each character of the first string and use .indexOf() to find its position in the second string, moving forward each time. If all characters in the first string appear in order, then it’s a subsequence.

Steps

Initialize a variable position to 0.
Loop through each character in the subsequence string.
For each character, use .indexOf(char, position) to find its position in the main string.
If the character is found, update position to the next index; if not, return false.
Return true if all characters are found in the correct order.

Time & Space Complexity

Time Complexity: O(n * m), where n is the length of the subsequence and m is the length of the main string.
Space Complexity: O(1), as only a few variables are used.

Code Snippet

Dry Run

Example input: "abc", "ahbgdc"

Loop through "abc":
- a at position 0 in "ahbgdc" → update position to 1
- b at position 2 in "ahbgdc" → update position to 3
- c at position 5 in "ahbgdc" → update position to 6
All characters found in sequence, return true

Final output: true

Alternative Approach - Using Two Pointers

Approach

We can use two pointers to track positions in both strings. Move both pointers when characters match; if not, only advance the pointer in the main string. If we reach the end of the subsequence string, it is a subsequence.

Steps

Initialize two pointers: i = 0 for the subsequence and j = 0 for the main string.
Loop while both pointers are within the bounds of their respective strings.
If subStr[i] matches mainStr[j], increment i.
Always increment j to move through the main string.
If i reaches the end of subStr, return true; otherwise, return false.

Time & Space Complexity

Time Complexity: O(n + m), where n is the length of subStr and m is the length of mainStr.
Space Complexity: O(1), since only pointers are used.

Code Snippet

Dry Run

Example input: "abc", "ahbgdc"

Initialize: i = 0, j = 0
Loop:
- a === a → increment i to 1, j to 1
- h (no match) → increment j to 2
- b === b → increment i to 2, j to 3
- g (no match) → increment j to 4
- d (no match) → increment j to 5
- c === c → increment i to 3, j to 6
i === subStr.length, so return true

Final output: true

Complexity Analysis

JavaScript Method (Using String Methods)

Time Complexity: O(n * m)
Space Complexity: O(1)

Alternative Approach (Using Two Pointers)

Time Complexity: O(n + m)
Space Complexity: O(1)

Conclusion

Determining if one string is a subsequence of another can be achieved by searching for each character in sequence or by using two pointers. The two-pointer approach is more efficient, with linear time complexity.

Previous Next