Reformat The String - Video Solutions

Problem Overview: You receive a string containing lowercase letters and digits. The task is to rearrange the characters so letters and digits strictly alternate. If such a rearrangement is impossible (difference between counts greater than 1), return an empty string. Order inside each category does not matter, but the final string must follow the alternating pattern.

Approach 1: Interleaving Lists Approach (O(n) time, O(n) space)

Separate characters into two lists: one for digits and one for letters. Iterate through the input string once and append each character to the correct list. If the absolute difference between their sizes exceeds 1, alternating is impossible and you immediately return an empty string.

Build the result by interleaving characters from the two lists. The list with more elements starts first. Use an index loop and append one element from each list alternately until all characters are consumed. This approach is easy to implement and very readable, which makes it a good first solution during interviews when working with string manipulation problems.

Approach 2: Two Pointer Approach (O(n) time, O(1) extra space)

This method rearranges characters more directly using index control. First count how many digits and letters exist. If the difference is greater than one, return an empty string. Decide which type should appear at index 0 based on which count is larger.

Convert the string to a mutable array and maintain two pointers: one for indices where digits should appear and one for indices where letters should appear. Traverse the array and swap misplaced characters with the next valid position tracked by the appropriate pointer. The pointers move forward by two positions each step because valid characters must appear at alternating indices.

This technique avoids building extra lists and keeps memory usage minimal. The logic resembles common two pointers patterns used in many string rearrangement problems, where pointers track valid placement positions rather than scanning sequentially.

Recommended for interviews: The Interleaving Lists approach is the most common answer because it is simple, deterministic, and clearly demonstrates understanding of counting and reconstruction. The Two Pointer approach shows stronger control over in-place operations and space optimization. Interviewers typically accept either solution, but writing the O(n) logic cleanly matters more than micro‑optimizing memory.