algoadvance

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. Input Constraints:
   • What are the constraints on the lengths of s and t?
   • Are the strings case-sensitive?
2. Character Set:
   • Do the input strings contain only lowercase alphabets?

Strategy

We can solve this problem using a two-pointer technique where we iterate through the characters of both strings simultaneously. Here’s the step-by-step strategy:

1. Initialize two pointers, i for s and j for t, both starting from the beginning (index 0).
2. Iterate through string t with the pointer j.
   • If s[i] equals t[j], increment i.
   • Always increment j irrespective of whether s[i] matches t[j].
3. If i reaches the length of s before or when j reaches the end of t, then all characters of s have been found sequentially in t, so return true.
4. If the end of t is reached and i is not equal to the length of s, return false.

Time Complexity

• Time Complexity: O(n + m), where n and m are the lengths of strings s and t respectively. This is because we are iterating through each string at most once.
• Space Complexity: O(1), as we are using a constant amount of additional space.

Code

def isSubsequence(s: str, t: str) -> bool:
    m, n = len(s), len(t)
    i, j = 0, 0
    
    while i < m and j < n:
        if s[i] == t[j]:
            i += 1
        j += 1
    
    return i == m

# Example Usage
print(isSubsequence("abc", "ahbgdc"))  # Expected output: True
print(isSubsequence("axc", "ahbgdc"))  # Expected output: False

Try our interview co-pilot at AlgoAdvance.com

• 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?