Leetcode 392: Is Subsequence

Input: The input consists of two strings, s and t.

Example: s = 'abc', t = 'ahbgdc'

Constraints:

• 0 <= s.length <= 100

• 0 <= t.length <= 10^4

• s and t consist only of lowercase English letters.

Output: The output is a boolean indicating whether s is a subsequence of t.

Example: Output: true

Constraints:

• The output should be true if s is a subsequence of t, otherwise false.

Goal: The goal is to check if string s can be derived from string t by deleting characters while preserving the order of the remaining characters.

Steps:

• Use two pointers to traverse both strings.

• Start with both pointers at the beginning of their respective strings.

• Move through string t and match characters with string s one by one.

• If all characters in s are matched in order, return true, otherwise return false.

Goal: Ensure the solution handles the constraints efficiently.

Steps:

• The solution must handle inputs with lengths up to 10^4 efficiently.

Assumptions:

• Both strings consist only of lowercase English letters.

• Input: Input: s = 'abc', t = 'ahbgdc'

• Explanation: Starting with pointers at the beginning of both strings, 'a' matches, then 'b' matches, and finally 'c' matches in order, so 'abc' is a subsequence of 'ahbgdc'.

• Input: Input: s = 'axc', t = 'ahbgdc'

• Explanation: Starting from the first letter of both strings, 'a' matches, but 'x' does not appear in order in 'ahbgdc', so 'axc' is not a subsequence of 'ahbgdc'.

Approach: The problem can be efficiently solved using a two-pointer technique to traverse both strings and check if all characters of s appear in t in the same order.

Observations:

• We need to check whether every character in string s can be found in order in string t.

• This problem can be solved efficiently with O(n) time complexity using two pointers to traverse both strings.

Steps:

• Initialize two pointers, one for each string s and t.

• Iterate through string t, checking if characters match the current character in string s.

• If a match is found, move the pointer in string s to the next character.

• Once all characters in s are found in t, return true; otherwise, return false.

Empty Inputs:

• When s is an empty string, it is always a subsequence of any string, so return true.

Large Inputs:

• The solution should handle the case where t is large (up to 10^4 characters).

Special Values:

• If s is longer than t, it is impossible for s to be a subsequence of t, so return false.

Constraints:

• The solution should be optimized to handle t with lengths up to 10^4 efficiently.

bool isSubsequence(string s, string t) {
    if(s == "") return true;
    int sdx = 0, tdx = 0;
    // sdx is sub seq of tdx

    for(; tdx < t.size(); tdx++) {
        if(t[tdx] == s[sdx]) sdx++;
        if(sdx == s.size()) return true;
    }
    return false;
}

1 : Function Definition

bool isSubsequence(string s, string t) {

Define the function 'isSubsequence' that takes two strings 's' and 't'. It will return a boolean value indicating whether 's' is a subsequence of 't'.

2 : Edge Case Handling

    if(s == "") return true;

Handle the edge case where 's' is an empty string. An empty string is considered a subsequence of any string, so return true.

3 : Variable Initialization

    int sdx = 0, tdx = 0;

Initialize two variables 'sdx' (for the index in string 's') and 'tdx' (for the index in string 't').

4 : For Loop

    for(; tdx < t.size(); tdx++) {

Start a for loop that iterates through each character in string 't' using 'tdx' as the index.

5 : Character Comparison

        if(t[tdx] == s[sdx]) sdx++;

Check if the current character of 't' matches the current character of 's'. If they match, increment 'sdx' to move to the next character in 's'.

6 : Subsequence Check

        if(sdx == s.size()) return true;

If all characters of 's' are found in 't' (i.e., 'sdx' reaches the size of 's'), return true, indicating that 's' is a subsequence of 't'.

7 : Return Statement

    return false;

If the loop completes and not all characters of 's' were found in 't', return false, indicating that 's' is not a subsequence of 't'.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) where n is the length of string t, since we only traverse the strings once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only use a constant amount of extra space.

Leetcode 392: Is Subsequence

Solution to LeetCode 392: Is Subsequence Problem

Explore →