Shortest Way to Form String - Solution & Explanation

Q: Is Shortest Way to Form String easy or hard?

Shortest Way to Form String is considered a medium difficulty problem. The greedy two-pointer simulation is straightforward once you recognize the subsequence pattern, but optimizing with preprocessing and binary search requires stronger algorithmic insight.

Q: Shortest Way to Form String Python/Java solution

Most implementations simulate subsequence matching with two pointers. Iterate through source while advancing a pointer in target whenever characters match. When the source scan finishes, increment the subsequence count and repeat until the entire target is formed or no progress is possible.

Q: How to solve Shortest Way to Form String in O(n)?

Strict O(n) is generally not achievable for arbitrary inputs because you must process every character of the target and potentially search within the source. The closest optimization preprocesses source positions and uses binary search, achieving O(m log n) time while avoiding repeated full scans of the source.

Q: What is the best approach for Shortest Way to Form String?

The greedy two pointers approach is the most common solution. Iterate through the source string while matching characters in the target, consuming as many as possible in each pass. Every full pass counts as one subsequence. The algorithm runs in O(n * m) time with O(1) extra space.

Q: Is Shortest Way to Form String asked at Google/Amazon/Meta?

Shortest Way to Form String is a common interview-style problem for companies like Google and Amazon. It tests subsequence reasoning, greedy strategy, and efficient string traversal. Variants may also appear in Meta-style interviews focusing on string preprocessing and binary search optimizations.

Q: What data structure is used in Shortest Way to Form String?

The basic solution uses two pointers to simulate subsequence matching between source and target. An optimized approach uses a hash map from character to sorted index list, combined with binary search to quickly find the next valid position in the source string.

Q: What is the time complexity of Shortest Way to Form String?

The typical greedy simulation runs in O(n * m) time, where n is the length of source and m is the length of target, because the source string may be scanned multiple times. A more optimized solution using preprocessed character indices and binary search runs in O(m log n) time with O(n) space.

MediumPremiumFree on FleetCodeTwo Pointers String Binary Search Greedy7 min readAsked at: Meta, Pinterest, Google

Practice this problem

Problem Statement

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.

Example 1:

Input: source = "abc", target = "abcbc"
Output: 2
Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".

Example 2:

Input: source = "abc", target = "acdbc"
Output: -1
Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.

Example 3:

Input: source = "xyz", target = "xzyxz"
Output: 3
Explanation: The target string can be constructed as follows "xz" + "y" + "xz".

Constraints:

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

Approach Overview

Problem Overview: You are given two strings: source and target. You can take subsequences of source and concatenate them to build target. The task is to compute the minimum number of subsequences required. If a character in target does not exist in source, forming the string is impossible.

Approach 1: Greedy Two Pointers (O(n * m) time, O(1) space)

Scan source repeatedly while consuming characters from target. Maintain a pointer i for target. For each pass through source, iterate with a second pointer and match characters whenever source[j] == target[i]. Each full scan represents using one subsequence of source. If a full scan makes no progress (the target pointer does not move), the required character does not exist in source, so return -1. The greedy insight: always consume as many target characters as possible in each pass. This approach uses two pointers and works well because subsequences preserve order but allow skipping characters.

Approach 2: Preprocessed Indices + Binary Search (O(m log n) time, O(n) space)

Preprocess source by storing indices of each character in a map (for example, char → sorted list of positions). Traverse target while tracking the last used index in source. For each character, run a binary search on its index list to find the smallest position greater than the previous one. If such a position exists, continue the current subsequence. Otherwise, start a new subsequence and pick the first occurrence of that character. This reduces repeated scans of the entire source string and uses the monotonic index property to jump efficiently. The idea combines string processing with binary search over precomputed positions.

Recommended for interviews: The greedy two-pointer method is the expected baseline. It shows you understand subsequences and can simulate the process efficiently. Mentioning the indexed + binary search optimization demonstrates deeper understanding of performance tradeoffs and how to avoid repeated scans of the source string. Interviewers typically accept the two-pointer solution first, then discuss optimizations if the strings become very large.

Solution

We can use the two pointers method, where pointer j points to the target string target. Then we traverse the source string source with pointer i pointing to the source string source. If source[i] = target[j], then both i and j move one step forward, otherwise only pointer i moves. When both pointers i and j reach the end of the string, if no equal character is found, return -1, otherwise the subsequence count increases by one, and then set pointer i to 0 and continue to traverse.

After the traversal ends, return the subsequence count.

The time complexity is O(m times n), where m and n are the lengths of the strings source and target respectively. The space complexity is O(1).

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Greedy Two Pointers	O(n * m)	O(1)	Best general solution. Simple to implement and commonly expected in interviews.
Preprocessed Indices + Binary Search	O(m log n)	O(n)	Useful when the source string is large and repeatedly scanning it becomes expensive.

Video Solution

Shortest Way to Form String • Kevin Naughton Jr. • 29,262 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Way to Form String easy or hard?

Shortest Way to Form String is considered a medium difficulty problem. The greedy two-pointer simulation is straightforward once you recognize the subsequence pattern, but optimizing with preprocessing and binary search requires stronger algorithmic insight.

Shortest Way to Form String Python/Java solution

Most implementations simulate subsequence matching with two pointers. Iterate through source while advancing a pointer in target whenever characters match. When the source scan finishes, increment the subsequence count and repeat until the entire target is formed or no progress is possible.

How to solve Shortest Way to Form String in O(n)?

Strict O(n) is generally not achievable for arbitrary inputs because you must process every character of the target and potentially search within the source. The closest optimization preprocesses source positions and uses binary search, achieving O(m log n) time while avoiding repeated full scans of the source.

What is the best approach for Shortest Way to Form String?

The greedy two pointers approach is the most common solution. Iterate through the source string while matching characters in the target, consuming as many as possible in each pass. Every full pass counts as one subsequence. The algorithm runs in O(n * m) time with O(1) extra space.

Is Shortest Way to Form String asked at Google/Amazon/Meta?

Shortest Way to Form String is a common interview-style problem for companies like Google and Amazon. It tests subsequence reasoning, greedy strategy, and efficient string traversal. Variants may also appear in Meta-style interviews focusing on string preprocessing and binary search optimizations.

What data structure is used in Shortest Way to Form String?

The basic solution uses two pointers to simulate subsequence matching between source and target. An optimized approach uses a hash map from character to sorted index list, combined with binary search to quickly find the next valid position in the source string.

What is the time complexity of Shortest Way to Form String?

The typical greedy simulation runs in O(n * m) time, where n is the length of source and m is the length of target, because the source string may be scanned multiple times. A more optimized solution using preprocessed character indices and binary search runs in O(m log n) time with O(n) space.

Ready to solve this problem?

Practice Shortest Way to Form String with our built-in code editor and test cases.

Practice on FleetCode

Is Subsequence

Number of Matching Subsequences

Problem Info

DifficultyMedium

Acceptance61.6%

Approaches1

Reading time7 min

Asked at

Meta Pinterest Google