Problem statement

https://binarysearch.com/problems/Subsequence-Concatenation-to-Target/

Solution

The idea is for each letter found all places we have it and then use binary search. We also use trick of s + s, so when we do binary search we do not need to deal with cases when we out of bound: in this case just -n and add 1 to answer.

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

Remark

Similar to Leetcode 0466. Count The Repetitions