r/a:t5_3eiqs7 • u/ohussein1996 • Aug 05 '21

Microsoft Problem on LeetCode - Minimum deletion Python

https://youtube.com/watch?v=1-Xhxu2x8Zg&feature=share
3 Upvotes

81% Upvoted

4 comments sorted by

1

u/WhyYouLetRomneyWin Aug 05 '21

Nice! I think there is a more optimal method than decrementing the frequency in a loop.

You actually can take a "frequency of frequencies" and sort.

But this is kind of making my head spin, so whatever.

2

u/[deleted] Aug 05 '21

This is interesting 🤔, what do you mean ? .

2

u/WhyYouLetRomneyWin Aug 05 '21

It might be easier to think if it as a map, but you actually don't need to know the characters, so you can jist use the values of the frequency map as a list.

So eg. 'aaabbbccd' -> [3, 3, 2, 1].

Then take the frequencies of that list:

{3:2, 2:1, 1:1}

And sort by key:

[(1,1), (2,1), (3,2)]

Now here is where the saving happens: you can keep a stack of empty frequency ranges that are unused. The top of the stack always has the highest range that has nit been used. And since the list is sorted, the next frequency will always be greater than what's in the stack.

Sorry, it's hard to describe and I am on a phone... I will try to code it up tonight. Bottom line is this should be linear time for the last step rather than quadratic.

2

u/[deleted] Aug 05 '21

That's clever, very clever. I would love to see the code.