LC 1055 [M] Shortest Way to Form String - ALawliet/algorithms GitHub Wiki

we can do greedy because we do not disturb the relative positions of the characters

# two pointer greedy O(MN), O(1)
class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        matches = 0
        t = 0

        while t < len(target):
            # this has to go here to reset
            s = 0
            match_so_far = False

            while s < len(source) and t < len(target):
                if source[s] == target[t]: # char match
                    s += 1
                    t += 1
                    match_so_far = True
                else:
                    s += 1
                    
            # looped through all chars in s by now to build t
            if match_so_far == True: # full match
                matches += 1
            else: # got to the end and couldn't match
                return -1

        return matches