Problem of The Day: Is Subsequence

Problem Statement

Intuition

My initial thought is to iterate through the characters of t and check if each character matches the corresponding character in s. If I find a match, I can then iterate through the remaining characters of both strings to see if the entire s is present as a subsequence in t.

Approach

I will iterate through each character of t, and when I find a character that matches the first character of s, I will initiate a nested loop to compare the subsequent characters of both strings. If I successfully match all characters of s in order, then I can conclude that s is a subsequence of t.

Complexity

• Time complexity: O(m * n), where m is the length of s and n is the length of t. This is because in the worst case, I may need to traverse through all characters of t for each character in s.

• Space complexity: O(1) as I am not using any additional data structures that scale with the input size.

Code

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True
        for i, c in enumerate(t):
            if s and c == s[0]:
                idx_t = i
                idx_s = 0
                while idx_t < len(t):
                    if t[idx_t] == s[idx_s]:
                        idx_s += 1
                    idx_t += 1
                    if idx_s == len(s):
                        return True
        
        return False

Another Approach: buckets

This approach uses a dictionary to create “buckets” for each character in the second string, t. These buckets contain the indices where each character occurs in t.

Then, it iterates through the characters of the first string, s, in reverse order. For each character, it checks if there is a corresponding bucket in t. If so, it pops the last index from that bucket and ensures it is in a valid order relative to the previous character’s index.

If the indices are not in the correct order or the character is not present in t, the function returns False. If all characters are processed successfully, it returns True, indicating that s is a subsequence of t.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        buckets = defaultdict(list)
        for i, c in enumerate(t):
            buckets[c].append(i)

        idx = len(t)
        for c in reversed(s):
            if c not in buckets:
                return False

            while buckets and c in buckets and buckets[c]:
                i = buckets[c].pop()
                if i < idx:
                    idx = i
                    break
                else:
                    return False
                
            if not buckets[c]:
                del buckets[c]
        
        return True

Editorial Solution

Approach 2: Two-Pointers

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        LEFT_BOUND, RIGHT_BOUND = len(s), len(t)

        p_left = p_right = 0
        while p_left < LEFT_BOUND and p_right < RIGHT_BOUND:
            # move both pointers or just the right pointer
            if s[p_left] == t[p_right]:
                p_left += 1
            p_right += 1

        return p_left == LEFT_BOUND