NeetCode #29LC-1055MediumArrays & HashingNC Algo100
← Back to All Problems#29 · #1055 · Shortest Way to Form String(形成字符串的最短路径)
📌 Problem Statement & Constraints
Given a string
source and a string target, return the minimum number of subsequences of source whose concatenation equals target. If it is impossible, return -1. Constraints: 1 <= source.length, target.length <= 1000.💡 Core Algorithmic Approaches
- First check feasibility: every character of
targetmust exist insource, otherwise return-1. - Greedily use as many characters of
targetas possible in each pass oversource. - Each pass over
sourceconsumes a maximal prefix of the remainingtarget; when a pass consumes nothing, the target cannot be formed (already ruled out by the feasibility check). - The greedy is optimal because a single pass can only consume a prefix, and consuming the longest possible prefix can never hurt a later pass.
- A faster variant indexes the positions of each character in
sourceand uses binary search to jump directly to the next usable occurrence.
💻 Benchmark Python3 Implementation
class Solution:
def shortestWay(self, source: str, target: str) -> int:
have = set(source)
for ch in target: # feasibility check
if ch not in have:
return -1
passes = 0
i = 0 # position in target
n = len(target)
while i < n:
passes += 1
for ch in source: # one pass over source
if i < n and ch == target[i]:
i += 1 # consume greedily
return passes
# Faster variant: binary search over the positions of each character
class Solution2:
def shortestWay(self, source: str, target: str) -> int:
from bisect import bisect_left
from collections import defaultdict
pos = defaultdict(list)
for i, ch in enumerate(source):
pos[ch].append(i)
passes = 0
i = 0
n = len(target)
while i < n:
if target[i] not in pos:
return -1
passes += 1
j = 0 # next allowed index in source
while i < n:
lst = pos[target[i]]
k = bisect_left(lst, j)
if k == len(lst):
break # need a new pass
j = lst[k] + 1
i += 1
return passes⚡ Complexity Deep Dive
⏱️ Time Complexity
O(|source| * passes) for the simple version, where passes <= |target|. The binary-search variant is O(|target| * log |source|), which is faster when source is long.
💾 Space Complexity
O(1) for the simple version; O(|source|) for the position index in the fast variant.
⚠️ Interview Pitfalls & Follow-ups
- Skipping the feasibility check: without it, a target character missing from
sourcecauses an infinite loop (the pass consumes nothing, soinever advances). - Assuming the answer is
ceil(|target| / |source|): the characters need not match, so the count depends on the actual content. - Substring rather than subsequence: the problem is about subsequences, so the characters need not be contiguous.
- Trying a DP over prefixes: O(|source| * |target|) and far more complex than the greedy.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.