Sorting Piece by Piece

Hard

You are given two digit strings of equal length, start and goal. You may apply the following action to start any number of times: pick any non-empty piece of consecutive characters and sort its digits in ascending order, leaving the rest of the string as it is. For example, sorting the piece 826 in 58263 gives 52683. Return True if start can be turned into goal, and False otherwise.

Example 1

start="5132", goal="1352" → True

Sort the first three digits 513 into 135, which gives 1352.

Example 2

start="4401", goal="0441" → True

Sort the piece 440 into 044 to get 0441.

Example 3

start="123", goal="132" → False

Sorting never moves a larger digit in front of a smaller one, so 3 can never get ahead of 2.

Constraints

len(start) == len(goal)
1 ≤ len(start) ≤ 10⁵
Both strings consist of digits only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String Sorting

Similar problems

Equal Letters Kept Apart Hard Distinct Word Shorthands Hard No Letter Facing Its Twin Hard Biggest Number From Pieces Medium No Twin Letters Side by Side Medium

Input

start="5132", goal="1352"

Expected

True

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