Mixing
Sort characters in a Python string by frequency
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
5
down vote
favorite
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
python python-3.x programming-challenge sorting time-limit-exceeded
edited Sep 3 at 19:49
200_success
124k14144401
asked Sep 3 at 19:09
loremIpsum1771
25917
add a comment |Â
up vote
5
down vote
favorite
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
python python-3.x programming-challenge sorting time-limit-exceeded
edited Sep 3 at 19:49
200_success
124k14144401
asked Sep 3 at 19:09
loremIpsum1771
25917
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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
python python-3.x programming-challenge sorting time-limit-exceeded
edited Sep 3 at 19:49
200_success
124k14144401
asked Sep 3 at 19:09
loremIpsum1771
25917
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
python python-3.x programming-challenge sorting time-limit-exceeded
edited Sep 3 at 19:49
200_success
124k14144401
asked Sep 3 at 19:09
loremIpsum1771
25917
edited Sep 3 at 19:49
200_success
124k14144401
edited Sep 3 at 19:49
200_success
124k14144401
edited Sep 3 at 19:49
200_success
124k14144401
124k14144401
asked Sep 3 at 19:09
loremIpsum1771
25917
asked Sep 3 at 19:09
loremIpsum1771
25917
asked Sep 3 at 19:09
loremIpsum1771
25917
25917
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
9
down vote
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
answered Sep 3 at 19:49
Martin R
14.6k12258
1
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?
– Oddthinking
Sep 4 at 2:31
2
@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).
– Martin R
Sep 4 at 6:24
joinis a bit faster when provided with alistrather than agenerator, so I would write"".join([...). Other than that, excellent answer, +1.
– Ev. Kounis
Sep 4 at 7:33
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
If you prefer functional style you can also useitertools.starmapandoperator.mul(orstr.__mul__):return "".join(starmap(operator.mul, Counter(s).most_common())).
– David Foerster
Sep 4 at 9:26
add a comment |Â
up vote
6
down vote
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
answered Sep 3 at 19:44
3xi
914
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
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
answered Sep 3 at 19:49
Martin R
14.6k12258
1
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?
– Oddthinking
Sep 4 at 2:31
2
@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).
– Martin R
Sep 4 at 6:24
joinis a bit faster when provided with alistrather than agenerator, so I would write"".join([...). Other than that, excellent answer, +1.
– Ev. Kounis
Sep 4 at 7:33
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
If you prefer functional style you can also useitertools.starmapandoperator.mul(orstr.__mul__):return "".join(starmap(operator.mul, Counter(s).most_common())).
– David Foerster
Sep 4 at 9:26
add a comment |Â
up vote
9
down vote
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
answered Sep 3 at 19:49
Martin R
14.6k12258
1
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?
– Oddthinking
Sep 4 at 2:31
2
@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).
– Martin R
Sep 4 at 6:24
joinis a bit faster when provided with alistrather than agenerator, so I would write"".join([...). Other than that, excellent answer, +1.
– Ev. Kounis
Sep 4 at 7:33
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
If you prefer functional style you can also useitertools.starmapandoperator.mul(orstr.__mul__):return "".join(starmap(operator.mul, Counter(s).most_common())).
– David Foerster
Sep 4 at 9:26
add a comment |Â
up vote
9
down vote
up vote
9
down vote
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
answered Sep 3 at 19:49
Martin R
14.6k12258
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
answered Sep 3 at 19:49
Martin R
14.6k12258
edited Sep 4 at 6:24
answered Sep 3 at 19:49
Martin R
14.6k12258
answered Sep 3 at 19:49
Martin R
14.6k12258
answered Sep 3 at 19:49
Martin R
14.6k12258
14.6k12258
1
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?
– Oddthinking
Sep 4 at 2:31
2
@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).
– Martin R
Sep 4 at 6:24
joinis a bit faster when provided with alistrather than agenerator, so I would write"".join([...). Other than that, excellent answer, +1.
– Ev. Kounis
Sep 4 at 7:33
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
If you prefer functional style you can also useitertools.starmapandoperator.mul(orstr.__mul__):return "".join(starmap(operator.mul, Counter(s).most_common())).
– David Foerster
Sep 4 at 9:26
add a comment |Â
1
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?
– Oddthinking
Sep 4 at 2:31
2
@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).
– Martin R
Sep 4 at 6:24
joinis a bit faster when provided with alistrather than agenerator, so I would write"".join([...). Other than that, excellent answer, +1.
– Ev. Kounis
Sep 4 at 7:33
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
If you prefer functional style you can also useitertools.starmapandoperator.mul(orstr.__mul__):return "".join(starmap(operator.mul, Counter(s).most_common())).
– David Foerster
Sep 4 at 9:26
1
1
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?
– Oddthinking
Sep 4 at 2:31
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?
– Oddthinking
Sep 4 at 2:31
2
2
@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).
– Martin R
Sep 4 at 6:24
@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).
– Martin R
Sep 4 at 6:24
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.– Ev. Kounis
Sep 4 at 7:33
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.– Ev. Kounis
Sep 4 at 7:33
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
@MartinR: Thanks, Martin. That makes sense.
– Oddthinking
Sep 4 at 8:31
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())).– David Foerster
Sep 4 at 9:26
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())).– David Foerster
Sep 4 at 9:26
add a comment |Â
up vote
6
down vote
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
answered Sep 3 at 19:44
3xi
914
add a comment |Â
up vote
6
down vote
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
answered Sep 3 at 19:44
3xi
914
add a comment |Â
up vote
6
down vote
up vote
6
down vote
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
answered Sep 3 at 19:44
3xi
914
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
answered Sep 3 at 19:44
3xi
914
answered Sep 3 at 19:44
3xi
914
answered Sep 3 at 19:44
3xi
914
answered Sep 3 at 19:44
3xi
914
914
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f203046%2fsort-characters-in-a-python-string-by-frequency%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
