algoadvance

Leetcode 392. Is Subsequence

Problem Statement

Given two strings s and t, return true if s is a subsequence of t, or 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).

Clarifying Questions

1. What should be returned if either s or t is an empty string?
   • If s is empty, it is trivially a subsequence of t, so return true.
   • If t is empty and s is not, return false since a non-empty string cannot be a subsequence of an empty string.
2. Are there any constraints on the length of s and t?
   • Both s and t consist only of lowercase English letters.
   • The length of s and t can be up to 10^4.

Strategy

1. Initialize pointers: Use two pointers, one for s (let’s call it i) and one for t (let’s call it j).
2. Iterate through t: Traverse the string t using the pointer j. Each time a character in t matches the character in s at pointer i, increment i.
3. Check for completion: If pointer i reaches the end of s (i == s.length()), it means all characters of s have been matched in order in t, so return true. Otherwise, return false.

Code

#include <iostream>
#include <string>

bool isSubsequence(const std::string& s, const std::string& t) {
    int i = 0;  // Pointer for s
    int j = 0;  // Pointer for t

    while (i < s.length() && j < t.length()) {
        if (s[i] == t[j]) {
            i++;
        }
        j++;
    }

    return i == s.length();
}

int main() {
    std::string s = "abc";
    std::string t = "ahbgdc";
    
    bool result = isSubsequence(s, t);
    std::cout << std::boolalpha << result << std::endl;  // Should print "true"
    
    return 0;
}

Time Complexity

• Time Complexity: O(n + m), where n is the length of s and m is the length of t. This is because we perform at most one pass through each string.
• Space Complexity: O(1), as we only use a few integer variables for pointers and the rest is constant space.

This solution is efficient and straightforward, making use of two-pointer technique which is appropriate given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?