Leetcode - Increasing Decreasing String Solution
Poor Man
- Published
- Updated
- Reading time
- 2 min read
- Length
- 322 words
Given a string s. You should re-order the string using the following algorithm:
- Pick the smallest character from
sand append it to the result. - Pick the smallest character from
swhich is greater than the last appended character to the result and append it. - Repeat step 2 until you cannot pick more characters.
- Pick the largest character from
sand append it to the result. - Pick the largest character from
swhich is smaller than the last appended character to the result and append it. - Repeat step 5 until you cannot pick more characters.
- Repeat the steps from 1 to 6 until you pick all characters from
s.
In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.
Return the result string after sorting s with this algorithm.
Example 1:
Text
Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"Example 2:
Text
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.Example 3:
Text
Input: s = "leetcode"
Output: "cdelotee"Example 4:
Text
Input: s = "ggggggg"
Output: "ggggggg"Example 5:
Text
Input: s = "spo"
Output: "ops"Constraints:
1 <= s.length <= 500scontains only lower-case English letters.
Solution in Python#
Python
from collections import Counter
class Solution:
def sortString(self, s: str) -> str:
s = dict(Counter(s).items())
result = ""
while any(s.values()):
for letter in sorted(s.keys()):
if s[letter]:
result+=letter
s[letter]-=1
for letter in reversed(sorted(s.keys())):
if s[letter]:
result+=letter
s[letter]-=1
return result