# https://leetcode.com/problems/is-subsequence/submissions/
class Solution:
    def isSubsequence(self, S: str, T: str) -> bool:
        S = '0' + S # for when S = ''
        T = '0' + T # for when T = ''
        
        i = 0
        for t in T:
            if t == S[i]:
                i += 1
                if i == len(S):
                    return True
        
        return False

class Solution_binarysearch:
    def isSubsequence_1(self, s, t):
        start = 0
        for i in range(len(s)):
            start = t.find(s[i],start) # O(logN) --> overall O(NlogN)
            if start==-1:
                return False
            start += 1
        return True

    def isSubsequence_2(self, s, t):
        for c in s:
            i = t.find(c)
            if i == -1:
                return False
            else:
                t = t[i+1:] # this is not good, it can take up to O(N) time as it involves string copying
        return True

from collections import Counter
class Solution_greedy:
    def isSubsequence(self, S: str, T: str) -> bool:
        s, t = 0, 0
        while s <= len(S) - 1 and t <= len(T) - 1:
            if S[s] == T[t]:
                s += 1
                t += 1
            else:
                t += 1
        return s > len(S) - 1
        
        # return not Counter(s) - Counter(t)
        # counter doesnt work!! it loses the sequential information