Abstract / Summary

Rearrange a string so no two same characters are next to each other if possible.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (1+ million submissions).

Typical patterns to solve this problem:

• Counting
• Greedy
• Hash Table
• Heap (Priority Queue)
• Sorting
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of rearranging a string so that no two adjacent characters are identical. It follows a greedy strategy: at each step it picks the most frequent character that is different from the character placed previously. The algorithm maintains a frequency map, builds the output incrementally, and stops early when no valid choice exists.

Frequency Counting

The first phase builds a histogram of character occurrences. A defaultdict with integer default values is used, allowing the count to be increased without explicit existence checks.

freq = defaultdict(int)
for c in s:
    freq[c] += 1

This step runs once over the input string, establishing the data structure that drives later decisions.

Initialization of State

Two variables are prepared before entering the main loop. previous holds the character that was appended most recently, starting as an empty string because no character has been placed yet. result accumulates the final rearranged string.

previous = ""
result = ""

Selection of the Next Character

Inside the loop, the algorithm scans the current frequency map to find the character with the highest remaining count that is not equal to previous. Two local variables, best and count, track the candidate character and its frequency during the scan.

best  = ""
count = 0
for k in freq:
    if k != previous and freq[k] > count:
        best = k
        count = freq[k]

If the scan finishes without finding a suitable character (best remains empty), the function returns an empty string, indicating that a valid rearrangement is impossible.

Updating the Result and Frequency Map

When a valid character is found, it is appended to result. Its count in the frequency map is decremented, and if the count drops to zero the entry is removed entirely. Deleting exhausted entries keeps the map size minimal, which reduces the work of subsequent scans.

result += best
freq[best] -= 1
if freq[best] == 0:
    del freq[best]

The previous variable is then updated to the character just placed, ensuring the next iteration respects the adjacency rule.

previous = best

Loop Termination

The while freq: condition drives the loop until the frequency map becomes empty, meaning all characters have been placed successfully. The early-return path handles the case where the algorithm cannot proceed, providing a clear signal to the caller.

Edge Cases Handled

When the input string is empty, the frequency map is empty from the start, so the loop body never executes and the function returns the initially empty result.

If the string consists of a single character, the frequency map contains one entry. The first iteration selects that character, decrements its count to zero, deletes the entry, and the loop ends with a correctly formed single-character result.

When all characters are identical, the first iteration places the character, but the subsequent scan finds no alternative because the only remaining entry matches previous. The algorithm detects this situation (best == "") and returns an empty string, correctly indicating impossibility.

For strings where a valid rearrangement exists but the most frequent character dominates, the greedy choice of the highest-frequency eligible character ensures that the dominant character is spaced out as much as possible, allowing the algorithm to succeed when a solution exists.

Performance Optimizations

The use of a hash-based frequency map provides constant-time updates and lookups for character counts. By deleting entries whose count reaches zero, the map shrinks over time, reducing the number of keys examined in each iteration of the selection loop. This dynamic pruning avoids unnecessary checks on exhausted characters.

The early-exit condition (if best == "": return "") prevents the algorithm from continuing once it becomes impossible to satisfy the adjacency constraint, saving work on inputs that cannot be rearranged.

Choosing the most frequent eligible character in each step maximizes the chance of completing the arrangement early, which in practice reduces the total number of iterations compared to a naïve random selection.

Overall, the implementation balances simplicity with effective use of mutable data structures to keep the runtime work proportional to the length of the input while minimizing overhead in each iteration.

Imagine that all the letters in a word are like little friends who want to stand in a line. The rule is that two of the same letters cannot stand right next to each other because they might get too noisy.

This code starts by counting up how many of each letter there are, like putting them into different colored buckets. Then, it starts building a brand new line. It looks at all the buckets and tries to pick a letter that is not the same as the one that just joined the line. After picking a letter, it takes one away from that bucket. If a bucket becomes empty, that letter is all finished being used. It keeps doing this, picking the most popular letter that is allowed to join next, until every single letter has a spot in the new line. It always remembers the letter it just placed so it does not make the mistake of picking it again immediately.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python		Java				TS
	WalkCCC	C++		Python		Java
	leetcode.ca	C++		Python		Java	Rust	Go
	LeetcodeHelp	C++		Python		Java
	Progiez	C++		Python		Java
github	BigEggStudy		C#
	black-shadows	C++
	charles-wangkai					Java
	everthis				JS
	halfrost							Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	ruoru						Rust
	shreymehul		C#
	sonugiri1043	C++
	suxrobGM		C#
	trung-hn			Python
	varunu28					Java
	vli02								C
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality