MediumTwo PointersStringBinary SearchGreedyUpdated Sep 2026

1055. Shortest Way to Form String

Asked at Pinterest

Difficulty

Medium

Time

O(m * n)

Space

O(1)

Pattern

Two Pointers

Companies

1

Problem

You are given two strings, source and target. A subsequence of source is any string you get by deleting zero or more characters from source while keeping the remaining characters in their original order. For example, "ac" is a subsequence of "abc", but "ca" is not.

Your job is to build target by gluing together some number of subsequences of source. The pieces are placed one after another, in order, and each piece must be a subsequence of source. Return the smallest number of pieces needed. If no combination of pieces can ever spell out target, return -1.

A piece may be empty in principle, but using empty pieces never helps, so you can ignore them. The same character of source may be reused in different pieces — each piece is a fresh pass over source.

Building target from pieces of source

sourceabc012The only characters we are allowed to use, in thisordertargetpiece 1 = abcpiece 2 = bcabcbc01234Two pieces cover the whole target, so the answer is 2
Each piece must be a subsequence of "abc". Here two pieces, "abc" and "bc", spell out the target.

Constraints

  • ●1 <= source.length, target.length <= 1000
  • ●source and target consist of lowercase English letters only

Examples

Example 1
Inputsource = "abc", target = "abcbc"
Output2
WhyTake "abc" as the first piece, then "bc" as the second. Both are subsequences of "abc", and together they spell "abcbc". One piece is not enough because "abcbc" is not a subsequence of "abc" (the second 'b' has no place to go).
Example 2
Inputsource = "abc", target = "acdbc"
Output-1
WhyThe letter 'd' never appears in "abc", so no subsequence of "abc" can ever contain it. The task is impossible.
Example 3
Inputsource = "xyz", target = "xzyxz"
Output3
WhySplit the target as "xz" + "y" + "xz". Each part is a subsequence of "xyz", and no split into 2 parts works, so 3 is the minimum.

Asked At

1 companies
CompanyDifficulty
PinterestMediumView all Pinterest questions →

How to Think About It

1

If some character of target never appears in source, the answer is -1 regardless of anything else.

2

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.

3

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.

4

If a whole pass over source matches nothing, a character is missing — return -1.

5

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).

Greedy pass over source

targetabcbc01234j startPass 1 over source matches a, b, c — j moves from 0 to3targetabcbc01234jPass 2 matches b, c — j reaches the end, so we stopcount += 1 per passif a pass matches nothing → -1answer = number of passes
In each pass we grab as many target characters as we can, then start a new pass.
ComplexityTime O(m * n)Space O(1)Each pass over source costs O(m) and we may need up to n passes, where m = len(source) and n = len(target).

What Trips People Up in Real Interviews

1

Missing the impossibility check, which makes the loop run forever when a character is absent.

2

Trying DP over all split points. Greedy is optimal here because each pass is independent.

3

Resetting the target pointer between passes — only the source pointer restarts.

4

Not offering the next-table optimization when the interviewer asks for better than O(m * n).

Solution Code

O(m * n) time
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 count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(m * n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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)`.