Problem statement

https://binarysearch.com/problems/Number-of-Concatenations-to-Create-Subsequence/

Solution

Equal to BinarySearch Subsequence Concatenation to Target.

Complexity

It is O(m log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, s, t):
        if set(t) - set(s): return -1
        idx = defaultdict(list)
        for i, x in enumerate(s+s):
            idx[x].append(i)

        n, ans, curr = len(s), 1, 0
        for x in t:
            curr = idx[x][bisect.bisect_left(idx[x], curr)] + 1
            if curr - 1 >= n:
                ans += 1
                curr -= n

        return ans