Sort Characters By Frequency - Leetcode 451 - Python

[@satyamjha68]

Solved it!! It has become my daily routine now . First thing I do after waking up is solving daily challenge. Even during college exams I follow this rigorously !!

[@sagaciousjunebug]

How long do you spend on a problem and what do you do when a problem is too difficult?

[@satyamjha68]

@@sagaciousjunebug Even I don't have definite answer for this. I still ask the same question with many people. I give the problem an hour then I see some hints . If I am still unable to solve it after another half hour , I look at the solution and add it to a list of revision question! Generally Hard with less than 60% acceptance rate is currently where I am facing issue.

[@nicolasguillenc]

you have become one of my favorite youtubers in the last month, thank you so much

[@leeroymlg4692]

in this specific problem, I believe it's more efficient to add the frequencies to a list and sort it. Because if you iterate through the range of s length, s can be as long as 5 * 10^5. meanwhile there can only be 52 different frequencies due to there only being 52 unique characters in the input. So sorting a list of 52 elements would be quicker

[@sriramchitta7400]

exactly what i am thinking

[@cannonkalra]

62*

[@anon_y_mousse]

I've done something similar to this in C. I wrote a simple jumble solver to check my answers, and even generated an alternate dictionary file where the words were sorted and followed by the unsorted matches. Which also made it easy to just grep for all the possible matches if I sorted the letters myself first. I find that C is significantly easier to use for string handling than Python.

[@ecchioni]

The difference between "adding" to a string and using a join is actually huge. My C# solution went from 1600ms to 64ms when I changed to StringBuilder. I used a PQ though to sort the counts.

[@kapilkhandelwal48]

I also thought of a priority queue to sorting this in terms of count then push it into the answer

[@AdrianCuet]

yeah in my case it went from 200ms to 50ms aprox, but had to recode what i ve done

[@varunpalsingh3822]

I solved this myself, all thanks to you navdeep😄

[@ranjeet_sohanpal]

what? I didn't know that this dude is Punjabi

[@MP-ny3ep]

Thank you for the daily leetcode problems. It helps a lot. Another great explanation as always!

[@davi_singh]

solved this using a hashmap and a heapq in python, needed to modify the priority a bit by multiplying by -1 to get the max num everytime but it worked :)

[@yaswanthkosuru]

You can reverse the result after using minheap itself

[@davi_singh]

@@yaswanthkosuru yup though reversing would be an O(n) operation right? Multiplying by -1 felt like a quicker way, though I could be wrong

[@32gigs96]

(f ^^ g) x = (f x, g x) f = concatMap (uncurry replicate) . sortBy (flip compare) . map (length ^^ head) . group . sortBy (flip compare) just a quick one liner that took a minute. Could use a Map for better perf ofc but couldn't be bothered as i was in the repl lol

[@thiagosdev]

Well, i did this: from queue import PriorityQueue class Solution: def frequencySort(self, s: str) -> str: count = {} for c in s: count[c] = count.get(c, 0) + 1 pq = PriorityQueue() for c, f in count.items(): pq.put((-f, c)) res = "" while not pq.empty(): f, c = pq.get() res += c * -f return res

[@trueArcticFox]

First -Thanks for detailed step-by-step solution! Second - Perhaps it will be useful for someone to see a one-line solution: return ''.join(i*j for i,j in sorted(Counter(s).items(), reverse=True, key=lambda x: x[1]))

[@vans4lyf2013]

Why is bucket sort O(n) instead of n^2? The second for loop is nested and can’t buckets have n items so shouldn’t that be n^2?

[@ayaanahmad1085]

In the worst case it should run O(n*2) times with this unless we have a check to prevent the loop running when the number of characters added to final string are > length of the string. So even if there is a string like "aaaaa". It will stop after first iteration since all characters are printed

[@Lost1nTranslation]

Thanks for uploading these

[@dumbpandabear7947]

Why is this solution slower than nlogn solutions that sort by frequency or use a priority queue if this i O(n)?

[@m.kamalali]

We have Counter of max size (low and upper case English letters) so sort is o(1) , and uses single dictionary (Counter) which if faster than using two(Counter &freq)

[@Marcox385]

Just got my first 5% in both runtime and memory usage lmao I'm getting worse by the day

[@TacticalDoge101]

IMO those stats are pretty inaccurate. If I submit the same solution twice, I would get 2 different scores, and the difference would be huge. So don't worry about the percentage, be happy that you were able to solve a problem on your own ;) If you can think of an optimal solution, great, if not, take a look at the hints.

[@barnetthan9391]

Are you concatenating strings instead of using something like stringbuilder? That would slow you down a lot

[@achan3073]

this is basically same as top K frequent elements

[@hirakhirak9119]

i am new to leetcoding, what would be the difficulty level of this question?

[@user-gh2gw8cx2b]

Like medium. It's a good example of bucket sort .

[@chrischika7026]

easy medium@@user-gh2gw8cx2b

[@levelup2014]

Why are most of these question in python does he do problems using JavaScript?

[@georgeg.9696]

I don't think that bucket sort is the bets answer here. It will have a space cost of O(n) and time O(n), where n is the len of s. Computing the frequences and sorting it will not exactly be O(nlogn) because the number of valid characters is at most 62, so we can say that sorting the frequences will be a constant time operation, so the time complexity will be only the time complexity of counting the chars frequency O(n)

[@ecchioni]

Technically the upper char limit is 2^16.

[@akshayiithyd]

Even I did what you did. However both the solutions will have same big O time complexity. For bucket sort approach, there will be only as many distinct counts in worst case, as the number of distinct letters, which cant be greater than 62, hence evern that is O(1) space

[@georgeg.9696]

@@ecchioni in this problem is only upper case, lower case english letters and digits

[@ecchioni]

@@georgeg.9696 Here yes, but the hard upper limit is UTF-16.

[@shubh9207]

Can someone please explain me how the bucket is storing int values in Ascending order? Is it the counter function which stores most frequent values first or what is it?

[@shubh9207]

No shiz I realized that we're iterating through each and every possible length in the last loop, damn so clever.

[@Garensonic]

If the interviewer asked that the same frequency characters were sorted alphabetically would there be a way to address that in Python

[@rajsuriyang3427]

nlogn solution runs faster in leetcode. WTF is happening?

[@maxpapirovnyk]

Thanks for explanation! in your solution we can move the multiply part to the buckets generation: buckets[cnt].append(char * cnt)

[@iamstudying389]

tc: 0(n) and sc: o(128) i.e. constant in cpp string frequencySort(string s) { string ans; int arr[128]={0} ; for(int i = 0 ; i0) { ans+= char(index); maxi--; } if(ans.size()==s.size()) break; } return ans; }

[@ninjaasmoke]

past few days seem to be easy questions

[@memeproductions4182]

Time complexity for sorting is not n log n since you sort the characters and their are 62 worst case, so that's O(62 log 62)

[@owlmostdead9492]

That’s medium?

[@chrischika7026]

yup but I would say easy medium

[@ibrahimalshubaily9520]

monthly subscription for courses pls

[@hundred_gaming123]

class Solution: def frequencySort(self, s: str) -> str: k = "" d = Counter(s) d = { k :v fork, v in sorted(d.items(),key = operator.itemgetter(1))} //sort by val in dict for val in d: k += val * d[val] return k[::-1]

[@shantanushukla1082]

Such a bad explanation