Reformat The String: Interleaving Letters and Digits

Given a string s containing only lowercase English letters and digits, reformat it so that no two adjacent characters are of the same type (letter next to letter, or digit next to digit). Return any valid reformatting, or return "" if it is impossible.

This is LeetCode 1417: Reformat The String, an easy problem that tests your ability to separate, count, and interleave two groups of characters.

The problem

You are given a mixed string like "a0b1c2" or "leetcode". Your job is to rearrange it so that letters and digits alternate. The order within each group does not matter, and any valid answer is accepted. If no valid arrangement exists, you return an empty string.

The key constraint: interleaving is only possible when the two groups differ in size by at most 1. If you have 5 letters and 2 digits, there is no way to alternate them without placing two letters next to each other somewhere.

The approach: separate, check, interleave

The solution breaks into three clean steps. First, split the input into two lists: one for letters and one for digits. Second, check whether interleaving is possible by comparing the sizes. Third, build the result by alternating characters from each list, starting with whichever list is longer.

Step-by-step walkthrough

The code

def reformat(s: str) -> str:
    letters = [c for c in s if c.isalpha()]
    digits = [c for c in s if c.isdigit()]

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

    if len(digits) > len(letters):
        letters, digits = digits, letters

    result = []
    for i in range(len(letters)):
        result.append(letters[i])
        if i < len(digits):
            result.append(digits[i])

    return ''.join(result)

The function starts by partitioning characters into two lists. If the sizes differ by more than 1, it returns "" immediately. Otherwise, it ensures letters is the longer (or equal-length) list by swapping if needed. Then it interleaves: for each character in the longer list, it appends one character, followed by one from the shorter list when available. The result naturally alternates types.

Complexity analysis

The separation pass is O(n), the feasibility check is O(1), and the interleaving pass is O(n). Total: O(n). Space is O(n) for the two lists and the result string. The brute force approach of trying all permutations is combinatorially explosive and completely impractical for strings longer than about 10 characters.

The building blocks

1. Character partitioning

Splitting a string into groups based on character type is a fundamental operation. You scan once and bucket each character:

group_a = [c for c in s if predicate_a(c)]
group_b = [c for c in s if predicate_b(c)]

This pattern appears whenever you need to process different character types separately before combining them. Examples include separating vowels from consonants, uppercase from lowercase, or letters from digits. The key insight is that partitioning first simplifies the recombination logic.

2. Feasibility check via counting

Before attempting to build a result, check whether one exists. For interleaving two groups with no adjacent duplicates, the rule is simple: abs(len(a) - len(b)) must be at most 1. This O(1) check saves you from attempting an impossible construction. The same pattern appears in problems like Reorganize String (where you check whether any character exceeds half the string length) and Task Scheduler (where you check whether the most frequent task forces idle slots).

Edge cases

All letters, no digits: "abc" has 3 letters and 0 digits. The difference is 3, which exceeds 1, so return "".

All digits, no letters: "123" similarly returns "" because there are no letters to interleave with.

Single character: "a" or "5" is already valid. One letter and zero digits differ by 1, which is allowed.

Counts differ by exactly 1: "ab1" has 2 letters and 1 digit. The larger group (letters) goes first, producing something like "a1b". This is the tightest valid case.

From understanding to recall

The separate-check-interleave pattern is simple enough to understand in one reading. But reproducing it under pressure requires more than understanding. You need to remember the feasibility condition (abs(len(a) - len(b)) > 1), the swap trick for always iterating over the longer list, and the single-loop interleaving logic.

These details are small but easy to fumble. Did you swap so the longer list comes first, or did you forget and iterate over the shorter one? Did you check > 1 or >= 1 for the feasibility condition? Spaced repetition drills these specifics until they are automatic. You see "interleave two groups with no adjacent same-type" and the code writes itself.

This problem also reinforces a general principle: when a problem involves two groups that need to alternate, always think "partition, check feasibility, interleave starting with the majority." That same mental framework applies to harder problems like Reorganize String and Task Scheduler, where the groups come from frequency counts rather than character types.

Related posts

• Longest Happy String - Similar greedy interleaving of characters with frequency constraints
• Reorganize String - Rearranging characters so no two adjacent are the same
• DI String Match - Building strings that satisfy character-by-character constraints