Fewest Subsequences of a Source String That Concatenate to a Target String

You are given two strings, source and target. A subsequence of source is any string obtained by deleting zero or more characters of source without changing the order of the characters that remain.

Return the minimum number of subsequences of source that, concatenated in order, form exactly target. If target cannot be formed this way, return -1.

In the reported screen this came in two stages: first decide only whether target can be formed at all, then compute the minimum number of subsequences. The function below answers both, with -1 meaning that it cannot be formed.

Function Signature

def min_subsequences_to_form(source: str, target: str) -> int:

Rules

• The same subsequence of source may be used any number of times, and each use counts separately.
• Every subsequence used must be non-empty.
• Characters are matched exactly.

Constraints

• 1 <= len(source) <= 1000
• 1 <= len(target) <= 1000
• source and target contain only lowercase English letters a to z.
• The result is either -1 or an integer from 1 to len(target) inclusive, and it is uniquely determined by the input.

Examples

Example 1

• Input: source = "cab", target = "abcab"
• Output: 2
• Explanation: "ab" and "cab" are both subsequences of "cab", and "ab" + "cab" = "abcab". One subsequence is not enough, because target is longer than source.

Example 2

• Input: source = "abc", target = "abd"
• Output: -1
• Explanation: d does not occur in source, so no concatenation of its subsequences can contain it.

Example 3

• Input: source = "xyz", target = "zyxz"
• Output: 3
• Explanation: One optimal split is "z" + "y" + "xz". Two pieces are impossible: in source, z comes after y and y comes after x, so no subsequence contains "zy" or "yx", and each of z, y and the following x must therefore start a new piece.

Fewest Source Subsequences to Build a Target

You are given two strings, source and target. A subsequence of source is any string obtained by deleting zero or more characters of source without changing the relative order of the characters that remain.

Return the minimum number of subsequences of source that, concatenated in order, form exactly target. If target cannot be formed this way, return -1.

This screen was asked in two stages: first decide only whether target can be formed at all, then compute the minimum number of pieces. Your function answers both at once: -1 means it cannot be formed, and any other value is the minimum count.

Rules:

• The same subsequence of source may be used any number of times; each use counts separately.
• Every subsequence used must be non-empty.
• Characters are matched exactly.

The answer is a single integer that is uniquely determined by the input: either -1, or an integer from 1 to len(target) inclusive.

Constraints:

• 1 <= len(source) <= 1000
• 1 <= len(target) <= 1000
• source and target contain only lowercase English letters a to z.

Example 1

Input:  source = "cab", target = "abcab"
Output: 2

"ab" and "cab" are both subsequences of "cab", and "ab" + "cab" = "abcab". One piece is not enough because target is longer than source.

Example 2

Input:  source = "abc", target = "abd"
Output: -1

d never occurs in source, so no concatenation of its subsequences can contain it.

Example 3

Input:  source = "xyz", target = "zyxz"
Output: 3

One optimal split is "z" + "y" + "xz". Two pieces are impossible: in source, z comes after y and y comes after x, so no subsequence contains "zy" or "yx".

Hints

1. If some letter of target never appears in source, no number of pieces can help. Otherwise, is the answer always finite?
2. When building one piece, is it ever worse to match each target character at the earliest possible position in source that is still available?
3. Precompute, for every index i of source and every letter, the next index at or after i where that letter occurs, so each target character is handled in O(1).

Approach

Greedy pass-by-pass matching is optimal. Build each piece by scanning source from left to right and matching the next character of target at the earliest position still available; when the current pass cannot absorb the next target character, close the piece and start a new pass from the beginning of source.

Why greedy is optimal: consider any optimal split. By an exchange argument, extending the first piece as far as possible never hurts: if the greedy first piece covers target[0:g] and an optimal first piece covers target[0:k] with k <= g, the remaining suffix target[g:] is a suffix of target[k:], and a suffix of a string formed by p pieces can be formed by at most p pieces (drop or trim the leading ones; trimming a subsequence from the front still leaves a subsequence). Induction over pieces gives that greedy uses no more pieces than optimal. Matching each character at the earliest available position is what lets a single pass absorb the longest possible prefix.

Feasibility: if every letter of target occurs somewhere in source, each character alone is a valid one-letter piece, so the answer is at most len(target). If some letter is missing, return -1.

Implementation: nxt[i][c] stores the smallest index j >= i with source[j] equal to letter c (or n when none), computed right to left in O(26 * n). Walking target keeps pos, the next usable source index for the current piece. If nxt[0][c] == n the letter is absent and the answer is -1; if nxt[pos][c] == n the current pass is exhausted, so the count increments and pos resets to 0; then pos = nxt[pos][c] + 1.

• Time complexity: O(26 * n + m), where n = len(source) and m = len(target)
• Space complexity: O(26 * n)