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.

Description Hints 4 Solution Video 11:25

1055. Shortest Way to Form String

Medium61.6% acceptance3 companiesPremium elsewhere, free here

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.

Asked at 3 companies

Google Meta

Topics

Hints open one at a time

Hint 1

Which conditions have to been met in order to be impossible to form the target string?

Hint 2

If there exists a character in the target string which doesn't exist in the source string then it will be impossible to form the target string.

Hint 3

Assuming we are in the case which is possible to form the target string, how can we assure the minimum number of used subsequences of source?

Hint 4

For each used subsequence try to match the leftmost character of the current subsequence with the leftmost character of the target string, if they match then erase both character otherwise erase just the subsequence character whenever the current subsequence gets empty, reset it to a new copy of subsequence and increment the count, do this until the target sequence gets empty. Finally return the count.

11:25

Still stuck?Read the written solution, or watch a walkthrough.

Open solution