LeetCode 1055: Shortest Way to Form String

Problem Restatement

A subsequence of a string is formed by deleting some (or no) characters without changing the order.

We are given two strings source and target.

We need to form target by choosing the minimum number of subsequences of source and concatenating them.

Return the minimum number of subsequences needed, or -1 if it is impossible.

The official constraints state that 1 <= source.length, target.length <= 1000.

Input and Output

Function shape:

def shortestWay(source: str, target: str) -> int:
    ...

Examples

Example 1:

source = "abc", target = "abcbc"

Use "abc" + "bc" (subsequence of "abc"). Two subsequences.

Answer:

2

Example 2:

source = "abc", target = "acdbc"

'd' is not in source. Impossible.

Answer:

-1

Key Insight

Check if all characters of target appear in source. If not, return -1.

Otherwise, greedily match target against source as many times as needed. Each time we exhaust source, start a new subsequence.

Algorithm

1. Check that every character in target appears in source.
2. Use two pointers: i for source, j for target.
3. For each character in target, advance i in source to find a match.
4. If i exhausts source, increment the count and reset i to 0.
5. Return the count.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        source_chars = set(source)
        for c in target:
            if c not in source_chars:
                return -1

        count = 1
        i = 0
        for c in target:
            while i < len(source) and source[i] != c:
                i += 1
            if i == len(source):
                count += 1
                i = 0
                while source[i] != c:
                    i += 1
            i += 1

        return count

Testing

def run_tests():
    s = Solution()

    assert s.shortestWay("abc", "abcbc") == 2
    assert s.shortestWay("abc", "acdbc") == -1
    assert s.shortestWay("xyz", "xzyxz") == 3

    print("all tests passed")

run_tests()