[LeetCode]#1370. Increasing Decreasing String

  1. Pick the smallest character from s and append it to the result.
  2. Pick the smallest character from s which is greater than the last appended character to the result and append it.
  3. Repeat step 2 until you cannot pick more characters.
  4. Pick the largest character from s and append it to the result.
  5. Pick the largest character from s which is smaller than the last appended character to the result and append it.
  6. Repeat step 5 until you cannot pick more characters.
  7. Repeat the steps from 1 to 6 until you pick all characters from s.
Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
  1. Convert string to list
  2. use temp.sort(key=lambda c: ord(c)) to sort string according ord(string)
  3. ord(‘a’)=97,ord(‘b’)=98…
  4. So we can get [‘a’,’b’,’c’]
  5. add ‘a’,’b’,’c’ to ans list and remove them from input list
  6. use temp.sort(key=lambda c: ord(c), reverse=True) to get [‘c’,’b’,’a’]
  7. add ‘c’,’b’,’a’ to ans list and remove them from input list.
  8. When s string are removed, return answer.
class Solution:
def sortString(self, s):
s = list(s)
ans = []
while s:
temp = list(set(s))
temp.sort(key=lambda c: ord(c))
for i in temp:
ans.append(i)
s.remove(i)
temp = list(set(s))
temp.sort(key=lambda c: ord(c), reverse=True)
for i in temp:
ans.append(i)
s.remove(i)
return ''.join(ans)
temp.sort(key=lambda c: ord(c))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store