Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which 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 s and append it to the result.
Pick the largest character from s which 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:
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:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:
Input: s = "leetcode"
Output: "cdelotee"

Example 4:
Input: s = "ggggggg"
Output: "ggggggg"

Example 5:
Input: s = "spo"
Output: "ops"

 
Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.

Difficulty: introductory

Starter code:

class Solution:
    def sortString(self, s: str) -> str:
        

Solutions:
class Solution:
    def sortString(self, s: str) -> str:
        sforward = sorted(s)
        sbackward = sforward[-1]
        
        suniq = ''
        
        for i in s:
            if i not in suniq:
                suniq += i

        suniq = sorted(suniq)
        
        max_count = 0
        
        for i in suniq:
            if s.count(i) > max_count:
                max_count = s.count(i)
        
        
        chr_count = [0 for i in range(len(suniq))]
           
        

        s_sort = ''
        
        for j in range(max_count):
            
            
            for i in range(len(suniq)):
                if chr_count[i] < s.count(suniq[i]):
                    s_sort += suniq[i]
                    chr_count[i] += 1
                else:
                    continue
                    
            suniq = suniq[::-1]
            chr_count = chr_count[::-1]
            
        
        return s_sort        
            


from collections import OrderedDict
class Solution:
    def sortString(self, s: str) -> str:
        
        s1 = OrderedDict()
        
        for i in s:
            
            if i in s1:
                s1[i] += 1
            else:
                s1[i] = 1
                
                
        reverse = 0
        t = []
        s1 = OrderedDict(sorted(s1.items()))
        print(s1)
        while(True):
            p = []
            for key,value in list(s1.items()):
                if value > 0:
                    s1[key] = value - 1
                    p.append(key)
            
            if p == []:
                break
            if reverse == 1:
                t += p[::-1]
            else:
                t += p
            reverse = 1 - reverse
            print(t)
        return (''.join(t))


class Solution:
    def sortString(self, s: str) -> str:
        output = []
        total = sorted(list(s))
        direction = 1
        while(len(total) > 0):
            if(direction == 1):
                selection = sorted(set(total))
            else:
                selection = sorted(set(total), reverse=True)
            direction *= -1
            output = output + list(selection)
            for char in selection:
                total.remove(char)
        return ''.join(output)
        
        
        
        



class Solution:
    def sortString(self, s: str) -> str:
        s = sorted(s)
        ans  = []
        while s:
            for i in sorted(list(set(s))):
                ans.append(s.pop(s.index(i)))
            
            for i in sorted(set(s),reverse=True):
                ans.append(s.pop(s.index(i)))
            
        
        return ''.join(ans)


class Solution:
    def sortString(self, s: str) -> str:
        s = sorted(s)
        ans  = []
        while s:
            for i in sorted(set(s)):
                ans.append(s.pop(s.index(i)))
            
            for i in sorted(set(s),reverse=True):
                ans.append(s.pop(s.index(i)))
            
        
        return ''.join(ans)

class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        d=Counter(s)
        asc=True
        ans=''
        while d:
            for i in sorted(d) if asc else sorted(d,reverse=True):
                ans+=i
                d[i]-=1
                if d[i]==0:
                    del d[i]
            asc^=True
        return ans

class Solution:
    collections.OrderedDict
    def sortString(self, s: str) -> str:
        list_s = list(s)
        list_s.sort()
        dict_s = {}
        for i in range(len(list_s)):
            if list_s[i] not in dict_s:
                dict_s[list_s[i]] = 1
            else:
                dict_s[list_s[i]] += 1
        result = []
        while dict_s != {}:
            i = 0
            while dict_s != {} and i < len(dict_s):
                result.append(list(dict_s)[i])
                if dict_s[list(dict_s)[i]] - 1 == 0:
                    del dict_s[list(dict_s)[i]]
                else:
                    dict_s[list(dict_s)[i]] -= 1
                    i += 1
            i = len(dict_s) - 1
            while dict_s != {} and i >= 0:
                result.append(list(dict_s)[i])
                if dict_s[list(dict_s)[i]] - 1 == 0:
                    del dict_s[list(dict_s)[i]]
                else:
                    dict_s[list(dict_s)[i]] -= 1
                i -= 1
        return ''.join(result)
        
        


class Solution:
    def sortString(self, s: str) -> str:
        output = []
        temp = sorted(list(s))

        while len(temp)>0:
            output.append(temp[0])
            temp.remove(temp[0])
            for e in temp:
                if e>output[-1]:
                    output.append(e)
                    temp[temp.index(e)] = ''
            temp = [e for e in temp if e]

            if len(temp)==0:
                break

            output.append(temp[-1])
            temp.remove(temp[-1])
            for i in range(len(temp)-1,0,-1):
                if temp[i]<output[-1]:
                    output.append(temp[i])
                    temp[i] = ''
            temp = [e for e in temp if e]

        return ''.join(output)

from collections import Counter
class Solution:
    def sortString(self, s: str) -> str:
        result = []
        s = sorted(s)
        counter = Counter(s)
         
        while s:
            for x in sorted(set(s)):
                s.remove(x)
                result.append(x)
            for x in sorted(set(s), reverse=True):
                s.remove(x)
                result.append(x)
        return ('').join(result)

class Solution:
    def sortString(self, s: str) -> str:
        res = ''
        s = list(s)
        s.sort()
        while s:
            i = 0
            curr = []
            while i < len(s):
                if s[i] not in curr:
                    curr.append(s.pop(i))
                else:
                    i += 1
            res += ''.join(curr)
            
            j = len(s)-1
            curr = []
            while j >= 0:
                if s[j] not in curr:
                    curr.append(s.pop(j))
                j -= 1
            res += ''.join(curr)
        return res

class Solution:
    def sortString(self, s: str) -> str:
        l=list(s)
        ope=list(s)
        s=''
        while(ope):
            temp=[]
            i=0
            temp2=list(set(ope))
            print('ji')
            while(ope and (ope) and temp2):
                n=min(temp2)
            
                if n not in temp:
                    temp.append(n)
                    ope.remove(n)
                    temp2.remove(n)
                print(temp)
                print((i,len(ope)))
                print(temp2)
                
                    
                i+=1
            s+=''.join(temp)
            temp=[]
            i=0
            temp2=list(set(ope))
            while( ope and len(ope) and temp2):
                n=max(temp2)
                if n not in temp:
                    temp.append(n)
                    ope.remove(n)
                    temp2.remove(n)
                i+=1
            s+=''.join(temp)
            
            
        return s
                
                
                


class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        counts, res, asc = Counter(s), [], True
        letters = sorted(set(s))
        while len(res) < len(s):
            for i in range(len(letters)):
                ch = letters[i if asc else ~i]
                if counts[ch] > 0:
                    res.append(ch)
                    counts[ch] -= 1
            asc = not asc
        return ''.join(res)

class Solution:
    def sortString(self, s: str) -> str:
        d = {}
        for c in s:
            if c not in d:
                d[c] = 1
            else:
                d[c] += 1
        self.d = d
        self.re = ''
        
        print((self.d))
        while True:
            if self.d == {}:break
            smallest = min(self.d)
            
            if smallest:
                self.re += smallest
                if self.d[smallest] == 1: del self.d[smallest]
                else: self.d[smallest] -= 1
            else:
                break
            
            while True:
                nexts = None
                for key in self.d:
                    if key > smallest:
                        if nexts is None:   nexts = key
                        else:
                            nexts = min(key, nexts)
                if nexts:
                    if self.d[nexts] == 1: del self.d[nexts]
                    else: self.d[nexts] -= 1
                    self.re += nexts
                else:
                    break
                smallest = nexts
                
            if self.d == {}:break

            biggest = max(self.d)
            
            if biggest:
                self.re += biggest
                if self.d[biggest] == 1: del self.d[biggest]
                else: self.d[biggest] -= 1
            else:
                break
            
            while True:
                nexts = None
                for key in self.d:
                    if key < biggest:
                        if nexts is None:   nexts = key
                        else:
                            nexts = max(key, nexts)
                if nexts:
                    if self.d[nexts] == 1: del self.d[nexts]
                    else: self.d[nexts] -= 1 
                    self.re += nexts
                else:
                    break
                biggest = nexts
                
        print((self.d))
        return self.re
            
            


class Solution:
    def sortString(self, s: str) -> str:
        new_list = []
        temp_list = list(s)

        while len(temp_list) > 0:

            if len(temp_list) == 0:
                break
            else:    
                slist = sorted(temp_list)
                temp_list = []
                new_list.append(slist.pop(0))
                for i in slist:
                    if ord(i) == ord(new_list[-1]):
                        temp_list.append(i) 
                    if ord(i) > ord(new_list[-1]):
                        new_list.append(i)
        
            
            if len(temp_list) == 0:
                break
            else:    
                slist = sorted(temp_list, reverse = True)
                temp_list = []
                new_list.append(slist.pop(0))
                for i in slist:
                    if ord(i) == ord(new_list[-1]):
                        temp_list.append(i) 
                    if ord(i) < ord(new_list[-1]):
                        new_list.append(i)
                        
        return ''.join(new_list)

class Solution:
    def sortString(self, s: str) -> str:
        x=sorted(s)
        res=''
        r=0
        while len(x)>0:
            if r==0:
                res+=x[0]
                x.remove(x[0])
                i=0
                while i<len(x):
                    if x[i]>res[-1]:
                        res+=x[i]
                        x.remove(x[i])
                    else:
                        i+=1
                x=x[::-1]
                r=1
            elif r==1:
                res+=x[0]
                x.remove(x[0])
                i=0
                while i<len(x):
                    if x[i]<res[-1]:
                        res+=x[i]
                        x.remove(x[i])
                    else:
                        i+=1
                x=x[::-1]
                r=0               
        return res
                


class Solution:
    def sortString(self, s: str) -> str:

        ss = sorted(list(dict.fromkeys(s)))
        ssr = ss+ss[::-1]
        dic ={}
        final_s =''
        for i in ss:
            dic[i] = 0
        for i in s:
            dic[i]+=1
        for i in range(len(s)):

            for j in ssr:
                if dic[j]>0:
                    final_s+=j
                    dic[j]-=1
     #       for x in ssr:
     #           if dic[x]>0:
      #              final_s+=x
     #               dic[x]-=1
        return final_s
                    
                
              


class Solution:
    def sortString(self, s: str) -> str:

        ss = sorted(list(dict.fromkeys(s)))
        ssr = ss[::-1]
        dic ={}
        final_s =''
        for i in ss:
            dic[i] = 0
        for i in s:
            dic[i]+=1
        for i in range(len(s)):

            for j in ss:
                if dic[j]>0:
                    final_s+=j
                    dic[j]-=1
            for x in ssr:
                if dic[x]>0:
                    final_s+=x
                    dic[x]-=1
        return final_s
                    
                
              


class Solution:
    def sortString(self, s: str) -> str:
        output = []
        temp = list(s)

        while len(temp)>0:
            temp.sort()
            output.append(temp[0])
            temp.remove(temp[0])
            for e in temp:
                if e>output[-1]:
                    output.append(e)
                    temp[temp.index(e)] = ''
            temp = [e for e in temp if e]

            if len(temp)==0:
                break
            temp.reverse()
            output.append(temp[0])
            temp.remove(temp[0])
            for e in temp:
                if e<output[-1]:
                    output.append(e)
                    temp[temp.index(e)] = ''
            temp = [e for e in temp if e]

            print(output)

        return ''.join(output)

class Solution:
    def sortString(self, s: str) -> str:
        output = []
        temp = list(s)
        dump = []

        while len(temp)>0:
            temp.sort()
            output.append(temp[0])
            temp.remove(temp[0])
            for e in temp:
                if e>output[-1]:
                    output.append(e)
                    temp[temp.index(e)] = ''
            temp = [e for e in temp if e]

            if len(temp)==0:
                break
            temp.reverse()
            output.append(temp[0])
            temp.remove(temp[0])
            for e in temp:
                if e<output[-1]:
                    output.append(e)
                    temp[temp.index(e)] = ''
            temp = [e for e in temp if e]

            print(output)

        return ''.join(output)

class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        counts = Counter(s)
        characters = sorted(set(s))
        ch_len = len(characters)
        total = 0
        res = ''
        while total < len(s):
            for i in range(ch_len):
                ch = characters[i]
                if counts[ch] > 0:
                    res += ch
                    total += 1
                    counts[ch] -= 1
            for i in range(ch_len)[::-1]:
                ch = characters[i]
                if counts[ch] > 0:
                    res += ch
                    total += 1
                    counts[ch] -= 1
        return res
       


class Solution:
    def sortString(self, s: str) -> str:
        s = list(s)
        ans = ''
        while s:
            for c in sorted(set(s)):
                ans += c
                s.remove(c)
            for c in sorted(set(s), reverse = True):
                ans += c
                s.remove(c)
        return ans


class Solution:
    def sortString(self, s: str) -> str:
        from collections import Counter
        counts, res, asc = Counter(s), [], True
        letters = sorted(set(s))
        while len(res) < len(s):
            for i in range(len(letters)):
                ch = letters[i if asc else ~i]
                if counts[ch] > 0:
                    res.append(ch)
                    counts[ch] -= 1
            asc = not asc
        return ''.join(res)


class Solution:
    def sortString(self, s: str) -> str:
        c = collections.Counter(''.join(sorted(s)))
        a = ''
        while c:
            stack = []
            for i in c.keys():
                if c[i] > 0:
                    a = a+i[0]
                    c[i] -= 1
                if c[i] > 0:
                    stack.append(i)
            while stack:
                j = stack.pop()
                a = a+j[0]
                c[j] -= 1
            c += Counter() # erases all counts of 0
        return a