A Note From Headline Cutouts

Medium

You are building a note message out of cut-out letters. You have as many copies of a newspaper as you like, all with the same headline headline. From one copy you may cut any letters of the headline, but they go into the note **in the same order** they had in the headline (each copy provides a subsequence of headline). Pieces from different copies are glued one after another. Return the smallest number of copies needed to build message, or -1 if it cannot be done.

Example 1

headline="rain", message="ranin" → 2

Cut "ran" (r, a, n) from the first copy and "in" from the second. Two copies suffice; one does not.

Example 2

headline="news", message="sun" → -1

The headline has no letter u, so the note cannot be made.

Example 3

headline="ab", message="bbb" → 3

Each copy yields just one b, so three copies are needed.

Constraints

1 ≤ len(headline), len(message) ≤ 1000
The strings consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Two Pointers String Binary Search

Similar problems

Stick Triples That Form a Triangle Medium Pieces Without Shared Letters Medium Best-Paid Gig for Each Worker Medium Greatest Interleave of Two Words Medium Swaps to the k-th Next Arrangement Medium

Input

headline="rain", message="ranin"

Expected

Run checks the first 3 tests in your browser. Submit checks all 158 tests on the server, hidden ones included.