Is Subsequence

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Determine whether string1 is subsequence of string2
• abc is subsequence of ambnc

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• If you remove unnecessary characters from string2 then would it become string1

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Strings
• Array
• Two Pointers

Time & Space Complexity

• Time: $O(len(s1)+len(s2))$ → Reason: Iterating over every element in both string once
• Space: $O(1)$ → Reason: Just storing pointers

Code

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # left, right = 0, 0

        # while left < len(s):
        #     while right < len(t) and s[left] != t[right]:
        #         right += 1
            
        #     if right == len(t):
        #         return False
        #     left += 1
        #     right += 1

        # return True

        pointer = 0
        for char in s:
            while pointer < len(t) and char != t[pointer]:
                pointer += 1
                
            if pointer == len(t):
                return False
            pointer += 1
        return True