5
\$\begingroup\$

I wrote a solution to the leetcode problem Sort characters by frequency and the solution passes 34/35 test cases. On the last test case, there is a "time limit exceeded" error with an input string of 100000+ "a" and "b" characters. How can the following code be optimized to handle an input of that size?

 def frequencySort(s):
        """
        :type s: str
        :rtype: str
        """
        freq = {}
        for i in s:
            if i in freq:
                freq[i] +=1
            else:
                freq[i] = 1
        output = ""
        newDict =  sorted(freq.items(), key=lambda kv: kv[1],reverse = True)
        for k,v in newDict:
            for i in range(v):
                output += k
        return output
\$\endgroup\$
10
\$\begingroup\$

The “set or increment dictionary value” logic

freq = {}
for i in s:
    if i in freq:
        freq[i] +=1
    else:
        freq[i] = 1

can be simplified using a defaultdict:

from collections import defaultdict

# ...

freq = defaultdict(int)
for i in s:
    freq[i] += 1

But instead of creating, updating and sorting your own dictionary you can use the built-in Counter class:

A counter tool is provided to support convenient and rapid tallies.

and its most_common() method:

Return a list of the n most common elements and their counts from the most common to the least.

That simplifies the code to

from collections import Counter


def frequencySort(s):
    """
    :type s: str
    :rtype: str
    """
    counter = Counter(s)
    output = "".join(char * freq for char, freq in counter.most_common())
    return output
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm new here, and don't yet know the local customs of codereview.SE. Would you normally also make PEP8 improvements by putting the function name in lower case and adding another newline before the def? \$\endgroup\$ – Oddthinking Sep 4 '18 at 2:31
  • 2
    \$\begingroup\$ @Oddthinking: Yes, and PEP8 improvements are in fact part of many answers to Python questions on CR. In this particular case, the function name is given by the LeetCode submission template, so that OP cannot change it. (But it would still be a valid point for a review. You can write an answer if you want.) – The missing newline before the def was my fault (there is no import statement in the original code). \$\endgroup\$ – Martin R Sep 4 '18 at 6:24
  • \$\begingroup\$ join is a bit faster when provided with a list rather than a generator, so I would write "".join([...). Other than that, excellent answer, +1. \$\endgroup\$ – Ev. Kounis Sep 4 '18 at 7:33
  • \$\begingroup\$ If you prefer functional style you can also use itertools.starmap and operator.mul (or str.__mul__): return "".join(starmap(operator.mul, Counter(s).most_common())). \$\endgroup\$ – David Foerster Sep 4 '18 at 9:26
6
\$\begingroup\$

The section:

for i in range(v):
    output += k

Can be rewritten as:

output += k*v

So that characters can be appended to the output in chunks this is much faster then doing it character by character

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.