Sorting a string to make a new one
<p>Here I had to remove the most frequent alphabet of a string(if frequency of two alphabets is same, then in alphabetical order) and put it into new string.</p>

<p>Input:</p>

<pre><code>abbcccdddd
</code></pre>

<p>Output:</p>

<pre><code>dcdbcdabcd
</code></pre>

<p>The code I wrote is:</p>

<pre><code>s = list(sorted(&lt;the input string&gt;))
a = []
for c in range(len(s)):
    freq =[0 for _ in range(26)]
    for x in s:
        freq[ord(x)-ord('a')] += 1
    m = max(freq)
    allindices = [p for p,q in enumerate(freq) if q == m]
    r = chr(97+allindices[0])
    a.append(r)
    s.remove(r)
print''.join(a)
</code></pre>

<p>But it passed the allowed runtime limit maybe due to too many loops.(There's another for loop which seperates the strings from user input)</p>

<p>I was hoping if someone could suggest a more optimised version of it using less memory space. </p>

<p>What about this?
I am making use of in-built python functions to eliminate loops and improve efficiency.</p>

<pre><code>test_str = 'abbcccdddd'

remaining_letters = [1]   # dummy initialisation
# sort alphabetically
unique_letters = sorted(set(test_str))
frequencies = [test_str.count(letter) for letter in unique_letters]

out = []

while(remaining_letters):

    # in case of ties, index takes the first occurence, so the alphabetical order is preserved  
    max_idx = frequencies.index(max(frequencies))    
    out.append(unique_letters[max_idx])

    #directly update frequencies instead of calculating them again
    frequencies[max_idx] -= 1  
    remaining_letters = [idx for idx, freq in enumerate(frequencies) if freq&gt;0]

print''.join(out)   #dcdbcdabcd
</code></pre>

python string python-2.7 sorting nested-loops