# Follow-up: Trade space for time and with binary search

1. For follow-up. Trade space for time. Store char positions for t.
s = aabac,
t = aaabaac.
{a: [0,1,2,4,5],
b: [3],
c: [6]}
2. Initialize lowerBound = 0. Iterate over s, binary search the first position of the current char satisfying position >= lowerBound, update lowerBound with the found position + 1.
3. Of course, you may use `bisect` instead of implementing `findFirstPos` https://docs.python.org/2/library/bisect.html

Please let me know if there is any mistake. Thanks.

``````class Solution(object):
def isSubsequence(self, s, t):
charPos = dict()
for pos, char in enumerate(t):
charPos.setdefault(char, []).append(pos)

lowerBound = 0
for char in s:
if char not in charPos:
return False
else:
firstPos = self.findFirstPos(charPos[char], lowerBound)
if firstPos == -1:
return False
else:
lowerBound = firstPos + 1
return True

def findFirstPos(self, poses, lowerBound):
low = 0
high = len(poses) - 1
while low < high:
mid = (high - low) / 2 + low
if poses[mid] >= lowerBound:
high = mid
else:
low = mid + 1
if poses[low] >= lowerBound:
return poses[low]
else:
return -1
``````

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