1051. Shortest Way to Form String

Medium
Two Pointers
String
Binary Search
Greedy

Description

Hints

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.

Statistics

Acceptance
61.5%
Submissions
176,787
Accepted
108,719