Python O(N) solution using Hash-Map.


  • 12
    G
    • Frequency of a character can vary from 0 to len(s).
    • Create a hashmap H1 of character to character frequency for the input string.
    • Iterate H1 to create hashmap H2 with key as frequency and value as substrings of repeated strings with length as the frequency.
    • Finally lookup all potential frequencies in decreasing order in H2 and produce the final result.
    from collections import Counter
    class Solution(object):
        def frequencySort(self, s):
            """
            :type s: str
            :rtype: str
            """
            c1, c2 = Counter(s), {}
            for k,v in c1.items():
                c2.setdefault(v, []).append(k*v)
            return "".join(["".join(c2[i]) for i in range(len(s), -1, -1) if i in c2])
    

  • 1

    Could use c2.setdefault(v, []).append(k*v).


  • 0
    G

    Good suggestions Stefan. I made the edits. However, at times I do argue that readability drops when we use the return value of setdefault.


  • 2

    Fun fact: I once said "I used setdefault a few times, then learned about defaultdict, and never looked back and I don’t want to. I think setdefault is the most confusing aspect of all of Python. And it’s ugly. I might be exaggerating. Slightly." Then again, later I wrote this solution and wrote "Looks like I’m getting the hang of it and it was just some irrational fear."

    Nowadays I like it and have no problem with it (and using it as imho intended, i.e., using the result value), though usually I still prefer defaultdict.

    That "".join is still unnecessary, btw, k*v already is a string.


  • 2
    G

    I personally prefer APIs which do just one thing and that one thing should be obvious by the API name. Unfortunately setdefault doesn't live up to that. With adequate practice, even poorly designed systems can give an illusion of intuition and ease. That is precisely the reason why you tolerate and endorse the usage of setdefault as is :)

    Good point about the redundant join - made the edit. Thanks!


  • 0

    nice solution, thanks for sharing


  • 1
    W

    Could you explain how the last step is O(n)?
    Ahh I see it's because there can be at max length of string s occurrences, so you just check H2 for length down to 0. Clever!


  • 0
    C

    @gabbu As Stefan said "usually I still prefer defaultdict", it seems that defaultdict is still a better choice here:
    c1, c2 = Counter(s), defaultdict(str)
    for k, v in c1.items(): c2[v] += k*v
    return ''.join(c2[i] for i in xrange(len(s),0,-1) if i in c2)

    Number of distinct characters could be much less than the string length. Sorting c1 by value would perform better than iterating the entire string when the string is long:
    return ''.join(map(lambda (k,v): k*v, sorted(c1.items(), key=itemgetter(1), reverse=True)))


  • 0
    G

    Would it be slower to use c1.most_common() instead of another container?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.