> < ~

class Solution:
    def sortString(self, s: str) -> str:
        ans = ''
        while (len(s) > 0): # step 7: repeat
            ans2, s = self.getSmall(s) #step 1-3
            ans += ans2
            if (len(s) == 0):
                return ans
            ans2, s = self.getBig(s) # step 4-6
            ans += ans2
        return ans

    def getSmall(self, s):
        min_s = min(s)
        ans = min_s # step 1
        i = s.index(min_s)
        s2 = s[:i] + s[(i+1):]
        s = s.replace(min_s, '')
        while (len(s) > 0): # step 3: repeat
            min_s = min(s)
            ans += min_s # step 2
            i = s2.index(min_s)
            s2 = s2[:i] + s2[(i+1):]
            s = s.replace(min_s, '')
        return ans, s2

    def getBig(self, s):
        max_s = max(s) # step 4
        ans = max_s
        i = s.index(max_s)
        s2 = s[:i] + s[(i+1):]
        s = s.replace(ans[-1], '')
        while (len(s) > 0): # step 6: repeat
            max_s = max(s)
            ans += max_s # step 5
            i = s2.index(max_s)
            s2 = s2[:i] + s2[(i+1):]
            s = s.replace(max_s, '')
        return ans, s2