# running time must be O(N), as you always have fixed array
# as one of the optimisations is keeping the exact occurrence in separate
# array, so you will not come across problem when a - 1 time, s - 1000000 times
# or more
def sortstring(str):
    # allocating list of ASCII characters
    # max is just for some kind of optimization, you can also nullify chars
    # that you already viewed, or something like that
    list, max = 128*[0], 0
    # collecting occurence of each character
    for i in range(len(str)):
        list[ord(str[i])] += 1
        max = list[ord(str[i])] if max <  list[ord(str[i])] else max
    res = ""
    # go though potential number of occurrences
    # and collect chars, as they are already sorted by char index
    # in Java I would use some sort of StringBuffer, if you are dealing with
    # very large strings
    for i in range(1, max+1):
        for j in range(len(list)):
            if list[j] == i:
                res += chr(j)*i
    return res