# Easy to understand binary search solution

• ``````from collections import defaultdict
from bisect import bisect_left
class Solution(object):

def createMap(self, s):
# create a map. key is char. value is index of apperance in acending order.
posMap = defaultdict(list)
for i, char in enumerate(s):
posMap[char].append(i)
return posMap

def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
posMap = self.createMap(t)
# lowBound is the minimum index the current char has to be at.
lowBound = 0
for char in s:
if char not in posMap: return False
charIndexList = posMap[char]
# try to find an index that is larger than or equal to lowBound
i = bisect_left(charIndexList, lowBound)
if i == len(charIndexList): return False
lowBound = charIndexList[i] + 1
return True
``````

• Brilliant! This solution is more efficient for the follow up question.

• Great solution. The straightforward solution in other threads would have time complexity O(k*len(t)) and space O(1) for the follow-up question. This one (with preprocessed t) has time complexity O(log(len(t)) * sum(len(Sk)) + len(t)) and space complexity O(len(t)). This solution trades memory for speed. Correct me if I am wrong.

• @WKVictor I think the time complexity for method hashing is more like `Max( len(t), log(len(t)) * k * len(s) )`, instead of `O(log(len(t)) * sum(len(sk)) + len(t))`. Cause if we scan sequence t from beginning to end, and add the indices to character hash, we already guaranteed the indices to appear in ascending order. So if we use a container like `vector` to store the indices, hash construction should only take ~ `len(t) * amortized O(1)`, aka `O(len(t))` time. And the binary search part still takes `O(log(len(t)) * len(sk))`.

• @WKVictor seems this could be a bit simpler

space complexity is length of t, we need to add an index value to our dictionary foreach element of t. You also have the overhead of the keys for t but this does not changed that fact that this is still O(length of t)

time complexity is 1 binary search through 1 dictionary entry for each character of s. Worst case the dictionary entry has all indexes of t so it's cost would be log of the length of t. Multiply that against length of s and you get O(length of s * log(length of t))

• ``````        if i == len(charIndexList): return False
``````

Can you please explain why we need to check this ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.