class Solution(object):
def sortString(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord('a')] += 1
ans = ""
while n > 0:
for i in range(26):
if cnt[i] > 0:
ans += chr(ord('a') + i)
cnt[i] -= 1
n -= 1
for i in range(25, -1, -1):
if cnt[i] > 0:
ans += chr(ord('a') + i)
cnt[i] -= 1
n -= 1
return ans