Shortest Way to Form String
Asked at Pinterest
Problem
Shortest Way to Form String asks for the minimum number of subsequences of source that, concatenated, form target — or -1 if impossible. A greedy two-pointer pass works: take as much of target as possible from each pass over source.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Pinterest questions → |
How to Think About It
If some character of target never appears in source, the answer is -1 regardless of anything else.
Key insight: greedily match as many characters of target as possible in each pass through source. Taking a character later rather than now can never help, because the next pass starts fresh.
Two pointers: walk source with i and target with j; when characters match, advance j. When source is exhausted, count one subsequence and restart i.
If a whole pass over source matches nothing, a character is missing — return -1.
Faster version: precompute next[i][c] = next index >= i in source holding character c. Each target character is then O(1), giving O(26 * m + n).
Optimal Approach
Step 1: count = 0, j = 0.
Step 2: While j < len(target):
start = j
For each char in source: if j < len(target) and it equals target[j], j += 1.
If j == start, return -1.
count += 1.
Step 3: Return count.
Time: O(m * n) worst case. Space: O(1).
What Trips People Up in Real Interviews
Missing the impossibility check, which makes the loop run forever when a character is absent.
Trying DP over all split points. Greedy is optimal here because each pass is independent.
Resetting the target pointer between passes — only the source pointer restarts.
Not offering the next-table optimization when the interviewer asks for better than O(m * n).
Solution Code
def shortestWay(source, target):
count = 0
j = 0
while j < len(target):
start = j
for ch in source:
if j < len(target) and ch == target[j]:
j += 1
if j == start:
return -1
count += 1
return countFrequently Asked Questions
What is the Shortest Way to Form String problem?
Shortest Way to Form String asks for the minimum number of subsequences of `source` that, concatenated, form `target` — or `-1` if impossible. A greedy two-pointer pass works: take as much of `target` as possible from each pass over `source`.
How do you solve Shortest Way to Form String?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Shortest Way to Form String?
Shortest Way to Form String is asked at Pinterest. It is a medium difficulty problem.
What are common mistakes on Shortest Way to Form String?
- Missing the impossibility check, which makes the loop run forever when a character is absent.
- Trying DP over all split points. Greedy is optimal here because each pass is independent.
- Resetting the target pointer between passes — only the source pointer restarts.
- Not offering the `next`-table optimization when the interviewer asks for better than `O(m * n)`.