Commitba2e092

authored

Merge pull requestneetcode-gh#2899 from tahzeer/main-1

Create 0767-reorganize-string.cpp

2 parentsd57c279 +8495ce9 commitba2e092Copy full SHA for ba2e092

File tree

+44

-0

lines changed

+44

-0

lines changed

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+// Time: O(NlogN)`
	`2`	`+// Space: O(N)`
	`3`	`+`
	`4`	`+classSolution {`
	`5`	`+public:`
	`6`	`+ stringreorganizeString(string s) {`
	`7`	`+ string res="";`
	`8`	`+`
	`9`	`+ unordered_map<char,int> mp;`
	`10`	`+ priority_queue<pair<int,char>> maxh;`
	`11`	`+`
	`12`	`+for(auto ch : s)`
	`13`	`+ mp[ch] +=1;`
	`14`	`+`
	`15`	`+for(auto m : mp)`
	`16`	`+ maxh.push(make_pair(m.second, m.first));`
	`17`	`+`
	`18`	`+while(maxh.size() >1){`
	`19`	`+auto top1= maxh.top();`
	`20`	`+ maxh.pop();`
	`21`	`+auto top2 = maxh.top();`
	`22`	`+ maxh.pop();`
	`23`	`+`
	`24`	`+ res += top1.second;`
	`25`	`+ res += top2.second;`
	`26`	`+`
	`27`	`+if(--top1.first >0)`
	`28`	`+ maxh.push(top1);`
	`29`	`+`
	`30`	`+if(--top2.first >0)`
	`31`	`+ maxh.push(top2);`
	`32`	`+ }`
	`33`	`+`
	`34`	`+if(!maxh.empty()){`
	`35`	`+if(maxh.top().first >1)`
	`36`	`+return"";`
	`37`	`+`
	`38`	`+else`
	`39`	`+ res += maxh.top().second;`
	`40`	`+ }`
	`41`	`+`
	`42`	`+return res;`
	`43`	`+ }`
	`44`	`+};`

Comments

(0)