Abstract / Summary

Given a string, rearrange its letters and digits so that no two adjacent characters are the same type, or return an empty string if impossible.

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 53% (100k+ submissions).

Typical patterns to solve this problem:

• 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 defines a class Solution with a single method reformat. The method receives a string s that may contain digits and alphabetic characters. Its purpose is to rearrange the characters so that digits and letters strictly alternate. If such an arrangement is impossible, the method returns an empty string. The algorithm proceeds in three conceptual phases: separating the input into two collections, verifying that an alternating pattern can be formed, and constructing the final string by interleaving the two collections.

Splitting Characters

The first phase iterates over each character in the input string and distributes it into one of two lists, digits or letters. The test if "0" <= c <= "9" determines whether a character is a digit; otherwise it is treated as a letter. The code snippet below shows this partitioning step:

digits  = []
letters = []
for c in s:
    if "0" <= c <= "9":
        digits.append(c)
    else:
        letters.append(c)

By using simple list append operations, the method builds two separate sequences that preserve the original order of appearance for each character type.

Feasibility Check

After the split, the method evaluates whether an alternating arrangement is possible. The condition abs(len(digits) - len(letters)) > 1 captures the requirement that the counts of the two groups may differ by at most one. If the absolute difference exceeds one, the method immediately returns an empty string, indicating that no valid reformatting exists. This early exit prevents unnecessary work when the input cannot satisfy the alternating constraint.

if abs(len(digits) - len(letters)) > 1:
    return ""

Merging Process

When the feasibility condition is satisfied, the method proceeds to interleave the characters. It initializes an empty result string and decides which type should appear first based on the relative lengths of the two lists. The boolean pickDigit is set to True when there are at least as many digits as letters, ensuring that the longer group (or either when equal) leads the sequence. The merging loop continues until the result reaches the length of the original string. Inside the loop, the method appends the last element of the chosen list using pop(), then toggles pickDigit to switch the source for the next iteration.

result = ""
pickDigit = len(digits) >= len(letters)
while len(result) < len(s):
    result += digits.pop() if pickDigit else letters.pop()
    pickDigit = not pickDigit
return result

By popping from the end of each list, the algorithm avoids the overhead of removing elements from the front, which would be costly for Python lists. The alternating toggle guarantees that the final string respects the required digit-letter pattern.

Edge Cases Handled

The implementation gracefully handles several edge conditions. When the input consists solely of digits or solely of letters, the length difference exceeds one, triggering the early return of an empty string. When the input length is one, the feasibility check passes because the difference is zero, and the merging loop produces the single character unchanged. For inputs where the counts of digits and letters are equal, the method starts with a digit because the >= comparison makes pickDigit true; this deterministic choice yields a valid alternating string. When the counts differ by exactly one, the longer group is placed at the beginning, satisfying the alternating requirement without leaving any character unpaired.

Performance Optimizations

The code exhibits a few deliberate choices that improve runtime efficiency. The single pass used for splitting characters ensures linear processing relative to the input size. The early feasibility check prevents the more expensive merging step when it is known to be impossible, saving work for inputs with large imbalance. During merging, the use of list.pop() removes elements from the end of the list in constant time, avoiding the linear-time cost associated with pop(0) or slicing. Building the result string via repeated concatenation could be a concern in some languages, but Python’s internal string builder optimizes short incremental concatenations, and the total number of concatenations equals the length of the input, keeping the overhead modest. The toggle mechanism for selecting the source list is a simple boolean flip, which incurs negligible computational cost. Overall, the algorithm runs in linear time with respect to the length of the input string and uses only a few auxiliary data structures whose total size is proportional to the input.

Imagine you have a messy box filled with blocks. Some blocks have numbers written on them, and some have letters. The goal is to line them up in a row so that no two number blocks are touching each other and no two letter blocks are touching each other.

First, you pick up every piece from the box one by one. You look at it carefully. If it is a number, you put it into a bucket meant for numbers. If it is a letter, you put it into a bucket meant for letters.

Next, you check how many blocks you have in each bucket. If one bucket has way more blocks than the other, like having ten numbers but only one letter, you would never be able to keep them from touching. In that case, you just stop because it cannot be done.

If the numbers and letters are close enough in amount, it is time to build the line. You decide which bucket to pick from first based on which one has more blocks. You take a block out of that bucket and place it in the row. Then you switch to the other bucket and take a block from there. You keep switching back and forth, picking from one bucket and then the other, until all the blocks are in a neat, alternating line.

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++		Java		Python					TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python			Go	Rust	TS
	Progiez	C++		Java		Python
github	BigEggStudy						C#
	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim		JS
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	Krazune							C
	lkwq007					Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	JavaScript
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lkwq007	Python
varunu28	Java

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