Increasing Decreasing String
You are given a string s. Reorder the string using the following algorithm:
- Remove the smallest character from
sand append it to the result. - Remove the smallest character from
sthat is greater than the last appended character, and append it to the result. - Repeat step 2 until no more characters can be removed.
- Remove the largest character from
sand append it to the result. - Remove the largest character from
sthat is smaller than the last appended character, and append it to the result. - Repeat step 5 until no more characters can be removed.
- Repeat steps 1 through 6 until all characters from
shave been removed.
If the smallest or largest character appears more than once, you may choose any occurrence to append to the result.
Return the resulting string after reordering s using this algorithm.
Example 1
Input
s = "aaaabbbbcccc"Output
"abccbaabccba"After the first increasing and decreasing pass, the result is
abccba; repeating the process with the remaining characters produces abccbaabccba.Example 2
Input
s = "rat"Output
"art"The word
rat becomes art after re-ordering it with the mentioned algorithm.Constraints
- 1 <= s.length <= 500
- s consists of only lowercase English letters.