Reorganize String

Try to solve the Reorganize String problem.

We'll cover the following

Statement#

Given a string, str, rearrange it so that any two adjacent characters are not the same. If such a reorganization of the characters is possible, output any possible valid arrangement. Otherwise, return an empty string.

Constraints:

  • 1≤1\leq str.length ≤500\leq500
  • Input string consists of lowercase English letters.

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check that if you’re solving the correct problem:

Reorganize String

1

What is the output if the following string is given as input?

“programming”

(Select all that apply.)

A)

“programing”

B)

“rgmrgmpiano”

C)

“rmpimrggano”

D)

“programimng”

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Store each character and its frequency in a hash map.

Construct a max-heap using the character frequency data, so that the most frequently occurring character is at the root of the heap.

Iterate over the heap and in each iteration, pop the most frequently occurring character and append it to the result string.

Decrement the frequency of the popped character (since we have consumed one occurrence of it).

Push the popped character back onto the heap in the next iteration if the updated frequency is greater than 00.

Return the result string when the heap becomes empty.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Reorganize String

Solution: Kth Largest Element in a Stream

Solution: Reorganize String