Shortest Way to Form String

Shortest Way to Form String

What is this problem about?

The Shortest Way to Form String interview question gives you two strings source and target. Find the minimum number of subsequences of source needed to cover target (concatenated subsequences form target). Each subsequence greedily takes as many characters of target as possible from source. If any character in target doesn't appear in source, return -1.

Why is this asked in interviews?

Meta, Pinterest, and Google ask this problem because it requires greedy subsequence matching combined with binary search optimization. The greedy insight is: for each new "round," scan source to cover as many consecutive target characters as possible before starting the next round. Optimizing with binary search on precomputed character positions reduces O(|source| × |target|) to O(|target| × log|source|).

Algorithmic pattern used

Two approaches: greedy linear scan and binary search optimization. Greedy: maintain source_ptr and target_ptr. For each target character, advance source_ptr to find it in source (wrapping around means starting a new round). Count wraps as the number of subsequences used. Binary search: precompute positions[c] = sorted list of indices where character c appears in source. For each target character at source_pos, binary search for the next occurrence of that character in source after source_pos. If none found, wrap to the next round.

Example explanation

source = "abc", target = "abcbc".

Round 1: 'a' found at source[0], 'b' at source[1], 'c' at source[2]. Subsequence 1: "abc". Round 2: 'b' found at source[1], 'c' at source[2]. Subsequence 2: "bc".

Total rounds: 2.

source = "xyz", target = "xzy": 'x'→0, 'z'→2, 'y'→... no 'y' in source → return -1.

Common mistakes candidates make

• Not pre-checking that all target characters exist in source — iterating then failing mid-way gives a less clean solution.
• Counting wraps as rounds but not counting the final incomplete round — total rounds = wrap_count + 1 if any target characters remain.
• Using a linear scan on source for each target character — O(|source| × |target|) when binary search gives O(|target| × log|source|).
• Not resetting source_ptr correctly when wrapping to a new round.

Interview preparation tip

For the Shortest Way to Form String coding problem, the two-pointer binary search greedy string interview pattern is the efficient approach. The greedy invariant: always consume as many target characters as possible from each source traversal before starting a new one. Google and Pinterest interviewers appreciate the binary search optimization — precompute positions once, then bisect_right(positions[c], current_pos) gives the next occurrence in O(log n). Practice this "greedy matching with binary search position lookup" template — it generalizes to "minimum number of source copies to cover target" and related greedy string coverage problems.