- 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]} - 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.
- 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
```