Problem statement

https://leetcode.com/problems/shortest-way-to-form-string/

Solution

There are different time complexity algorithms, starting with O(mn) greedy and O(n log m) binary search.

The best algorithm is for every letter and index evaluate places of next occurences of this letter. Then we traverse our string T and on each step we do idx = d[ch][idx], it means that we look for index of element ch in S, starting from place idx.

  1. Check if idx >= len(S), if it is the case, it means that we reached the end of S, so we need to start from the beginning.
  2. Update idx = d[ch][idx].
  3. if idx < 0, it means, that we did not found symbol ch in the rest of our string, so we need to start new traversal and we indicate that we reached place d[ch][0] already.
  4. Increment idx by one.

Complexity

It is O(Q*n), where Q is the size of alphabet, that is O(26n) in our case to create d. Also we have m steps to traverse T. So, final time complexity is O(Q*n + m), where n is length of S and m is length of T. Space complexity is O(Q*n).

Code

class Solution:
    def shortestWay(self, S, T):
        def letter_get(letter, dr):
            n = len(S)
            res, cur = [0]*n, -n
            for i in range(n)[::dr]:
                if S[i] == letter: cur = i
                res[i] = cur
            return res

        S_set, T_set = set(S), set(T)
        if not T_set.issubset(S_set): return -1

        d = defaultdict(list)
        for symb in S:
            d[symb] = letter_get(symb, -1)

        idx, count = 0, 1
        for ch in T:
            if idx == len(S):
                count, idx = count + 1, 0
            idx = d[ch][idx]
            if idx < 0:
                count, idx = count + 1, d[ch][0]
            idx += 1
        return count

Remark

There is also O(mn) solution with two pointers dp and O(n log m) with binary search.