# 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

| Item | Meaning |
|---|---|
| Input | Strings `source` and `target` |
| Output | Minimum number of `source` subsequences to form `target`, or `-1` |

Function shape:

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

## Examples

Example 1:

```python
source = "abc", target = "abcbc"
```

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

Answer:

```python
2
```

Example 2:

```python
source = "abc", target = "acdbc"
```

`'d'` is not in `source`. Impossible.

Answer:

```python
-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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(|source| * |target|)` | Each target char scans source once |
| Space | `O(1)` | Constant pointers |

## 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

```python
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

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `"abc","abcbc"` | `2` | Two passes through source |
| Contains `'d'` | `-1` | Impossible |
| `"xyz","xzyxz"` | `3` | Three passes needed |