Watch 10 video solutions for Shortest Way to Form String, a medium level problem involving Two Pointers, String, Binary Search. This walkthrough by Kevin Naughton Jr. has 29,170 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000source and target consist of lowercase English letters.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.
| 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. |