⚡Flashcard Drill➔
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

  1. First check feasibility: every character of target must exist in source, otherwise return -1.
  2. Greedily use as many characters of target as possible in each pass over source.
  3. Each pass over source consumes a maximal prefix of the remaining target; when a pass consumes nothing, the target cannot be formed (already ruled out by the feasibility check).
  4. 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.
  5. A faster variant indexes the positions of each character in source and 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 source causes an infinite loop (the pass consumes nothing, so i never 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems