Check If String Is Transformable With Substring Sort Operations
01 · Problem
You are given two strings s and t of equal length, both made of digits. In one operation you may pick any non-empty substring of s and sort its digits in ascending order in place.
Return true if s can be turned into exactly t using any number of operations (including zero), otherwise return false.
02 · Examples
s = "53412", t = "35124"
true
Sort the substring "53" to get "35412", then sort the substring "412" to get "35124".
s = "4132", t = "1423"
true
Sort the substring "41" to get "1432", then sort the substring "32" to get "1423".
s = "1324", t = "3124"
false
In t the digit 3 sits before the 1, but in s the 1 is ahead of the 3. Sorting only ever moves a smaller digit forward past larger ones, so 3 can never overtake 1.
03 · Constraints
- 01s.length == t.length
- 021 <= s.length <= 105
- 03s and t consist only of digits '0' to '9'
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.