392. Is Subsequence

def is_subsequence(s, t):
    """Using Two Pointers / Greedy
    Time complexity: O(n + m)
    Space complexity: O(1)
    """
    if not s:
        return True
    if not t:
        return False

    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1

    return i >= len(s)

def is_subsequence(s, t):
    """Using iter()
    Time complexity: O(n + m)
    Space complexity: O(1)
    """
    # convert t into an iterator (will return one element at a time)
    # This prevents returning True in case all characters of s are in t but permuted
    remainder_of_t = iter(t)
    for char in s:
        if char not in remainder_of_t:
            return False
    return True

def is_subsequence(s, t):
    """one line variation of above"""
    remainder_of_t = iter(t)
    return all(c in remainder_of_t for c in s) # loops through to find the 1st False. Else returns True

def is_subsequence(s, t):
    """Using recursion
    Time Complexity: O(m+n)
    Space Complexity: O(1)
    """
    def helper(a, b):
        # base case
        if not a:
            return True
        if not b:
            return False
        
        # Recursion
        if a[-1] == b[-1]: 
            return helper(a[:-1], b[:-1]) 
        return helper(a, b[:-1]) 

    return helper(s,t)

# Although the statement can remind us of longest subsequence problems (see leetcode #1143)
# Dynamic Programming is too slow and not relevant here since there is no need to calculate anything

def is_subsequence(s, t):
    """Using Dynamic Programming (slow, not relevant here see leetcode #1143 instead)
    Time Complexity: O(mn)
    Space Complexity: O(mn)
    """
    if not s:
        return True
    if not t:
        return False

    n = len(s)+1
    m = len(t)+1
    
    dp = [[0]*(m) for _ in range(n)]

    for i in range(1, n):
        for j in range(1, m):
            if s[i-1] == t[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = dp[i][j-1]

    return dp[-1][-1] == len(s)

# If we check each Sk using above solution, then it would be k*O(m+n) time --> INEFICIENT
# The solution is to preprocess t and then do a binary search

# Option 1: iterative BS
def search_insert(arr, x):
    """Binary search to find the insert position of x in arr (iterative approach - See leetcode #35)"""
    # base cases
    if not arr or x <= arr[0]:
        return 0
    if arr[-1] < x:
        return len(arr)
    
    left = 0
    right = len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        if arr[mid] < x:
            left = mid+1
        else:
            right = mid-1
    return left


# Option 2: recursive BS
def search_insert_recur(self, arr, x):
    """Binary search to find the insert position of x in arr (recursive approach - See leetcode #35)"""
    def bs(left, right, x):
        nonlocal arr
        # base cases
        if left > right:
            return left
        mid = (left + right) // 2
        if x == arr[mid]:
            return mid

        # recursive relation
        if x < arr[mid]:
            return bs(left, mid - 1, x)
        return bs(mid + 1, right, x)

    return bs(0, len(arr)-1, x)


from collections import defaultdict

def is_subsequence(s, t):
    """Using binary search on ordered indexes (values) of Hashtable (where keys = char of s).
    Time Complexity:  O(n) + k* O(mlogn) with m = len(s) and n = len(t)
    Space Complexity: O(m)
    """
    indexes = defaultdict(list)  # values of dict[keys] will be lists AND default = []
    for i, char in enumerate(t):
        indexes[char].append(i)  # list all the indexes at which we find "element"

    start = 0
    for char in s:
        p = search_insert(indexes[char], start)  # char is present at [i1, i2, i3, ... , in]
        # but we only consider t[start:] --> i.e. could we insert 'start' inside [i1, ... , in]?
        if p == len(indexes[char]):  # if we could not (i.e. only at the end of t)
            return False
        start = indexes[char][p] + 1  # if we could, we now only consider t[p+1:]
    return True

from collections import defaultdict
from bisect import bisect_left

def is_subsequence(s, t):
    """Same as above but using method bisect_left (requires sorted argument)"""
    indexes = defaultdict(list)
    for i, char in enumerate(t):
        indexes[char].append(i)

    start = 0
    for char in s:
        p = bisect_left(indexes[char], start)
        if p == len(indexes[char]):
            return False
        start = indexes[char][p] + 1
    return True