Fewest Subsequences of a Source String That Concatenate to a Target String
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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
```python
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.
Overview: Given a source string and a target string, return the fewest subsequences of the source whose concatenation equals the target, or -1 when the target cannot be formed. It tests subsequence matching, greedy reasoning about why a choice is optimal, and an efficient iterative implementation.
Read the full Pinterest Software Engineer interview experience this question came from
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"`.
Constraints
- 1 <= len(source) <= 1000
- 1 <= len(target) <= 1000
- source and target contain only lowercase English letters 'a' to 'z'
- The result is -1 or an integer from 1 to len(target) inclusive, so it fits in a 32-bit signed int
Examples
Input: ('cab', 'abcab')
Expected Output: 2
Input: ('abc', 'abd')
Expected Output: -1
Hints
- If some letter of target never appears in source, no number of pieces can help. Otherwise, is the answer always finite?
- When building one piece, is it ever worse to match each target character at the earliest possible position in source that is still available?
- 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).
Community answers
Answer by akhil.gandhi10.ag
class Solution:
def shortestWay(self, source: str, target: str) -> int:
count = 0
target_idx = 0
while target_idx < len(target):
prev_idx = target_idx
for ch in source:
if target_idx < len(target) and ch == target[target_idx]:
target_idx += 1
if prev_idx == target_idx:
return -1
count += 1
return count