Reorganize String - Tesla Interview Question - Leetcode 767 - Python

0:00 - Read the problem
4:30 - Drawing Explanation
9:10 - Coding Explanation

leetcode 767

#tesla #coding #interview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[TheElementFive]

Conceptually simple but nuanced problems like these are my favorite

[sleepypanda]

I love this guy for his clarity. Within 5 mins I got the hint and also, I was doing the same mistake that you showed at first. Thanks a lot, I came up with the approach of priority queue after you gave the hint in the minute.

[poojabennabhaktula]

I have a FAANG interview this Thursday, almost gave up this question..even though it is frequently asked during interviews. Now that you've made a video on this ..I'm relieved

[cnknd]

Here's an alternative way to construct a rearrangement:
1. rearrange by frequency in descending order ('abbacca' -> 'aaabbcc')
2. break into two halves and merge in alternating order ('aaabbcc' -> 'aaab' + 'bcc' -> 'abacacb')

[VarunMittal-viralmutant]

Just to add a trivial check, in the beginning, when reorg is not possible:

maxF = max(count.values())

if maxF > (len(s) + 1) // 2:
return ""

Then we need not do the rest of heap algo ;)

[curesnow]

Thank you so much. I jumped straight to the solution because I don't know how to implement it after finishing reading the problem description.

[rushabhlegion]

I watched this video till 5:35 and was able to code it myself. Thanks.

C++ Guys:
class Solution {
public:
struct Compare{
bool operator()(pair<char, int>a, pair<char, int>b){
return a.second<b.second;
}
};
string reorganizeString(string s) {
unordered_map<char, int>mp;
for(int i=0;i<s.size();i++)
mp[s[i]]++;
priority_queue<pair<char, int>, vector<pair<char, int>>, Compare>pq;
for(auto it:mp)
pq.push({it.first, it.second});
string ans;
char prev='\0';
while(!pq.empty()){
pair<char, int>top=pq.top();
pq.pop();
if(top.first!=prev){
prev=top.first;
ans+=top.first;
top.second--;
if(top.second>0)
pq.push(top);
}
else if(!pq.empty()){
pair<char, int>top2=pq.top();
pq.pop();
prev=top2.first;
ans+=top2.first;
top2.second--;
if(top2.second>0)
pq.push(top2);
pq.push(top);
}
else
return "";
}
return ans;
}
};

[BootBoot-rlkv]

thanks for the great explanation, in just first 6 min understood how to solve problem

[osmanmusse]

Mate, we really love your videos doing also your explanation to some of these weird question. From London I hope you keep going with these videos.

[BieberTaylorLove]

Your videos motivate me to do leetcode, thanks 😊

[abdullahzia]

Ily neet, if I get a job from watching your videos imma send you a part of my first paycheck

[vaibhavrbs]

small clarification at 12:42 `if cnt < 0 ` wont work as cnt values are already (-ve), remember we are using maxheap in python..

[punnarahul]

congo bro on 50k i love watching your videos

[splendidbeaver]

Hi !
because of strings immutability in python, better use an array and join at the end for space efficiency

[EquinoXReZ]

The solution actually runs in O(nlogk) where k is the number of unique elements in s. Since s consists of only lower case letters this is constant so the heap solution is really O(n) TC and O(k) or O(1) SC

[abhishekrbhat]

wow when you explain it, the solution just clicks instantly

[eeee]

Hi NeetCode, I love binging your videos! Any chance of doing any of the calculator problems in the future?

[bokistotel]

Havent watched the video (used the hint ofcourse), and I googled the key = lambda item: item[1] if item[0] != previous_max[0] else float("-inf"). I knew what I want, but didnt know how to write it. I guess I also must remember that lambda syntax :(

My accepted solution

def reorganizeString(s: str) -> str:
# HINT: Alternate placing the most common letters.

s_freq = Counter(s) # {a:3, b:1}
previous_max = (None, None)
result = []
while s_freq:
max_key, max_val = max(
s_freq.items(),
key = lambda item: item[1] if item[0] != previous_max[0] else float("-inf")
)
if max_val == 0:
del s_freq[max_key]
else:
if previous_max[1] and len(s_freq) == 1:
return ""
previous_max = (max_key, max_val)
result.append(max_key)
s_freq[max_key] -=1

return "".join(result)

[jonaskhanwald]

Congratulations on reaching 50K subscribers. We need a live session on the occasion of 100K subscribers.

[oliesting]

Love your videos even though am not good with programming. Learning Python right now. Would love to listen to how to generate working code from plain English. Thanks