Reformat The String - Solution & Explanation
Problem Statement
You are given an alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).
You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.
Return the reformatted string or return an empty string if it is impossible to reformat the string.
Example 1:
Input: s = "a0b1c2" Output: "0a1b2c" Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.
Example 2:
Input: s = "leetcode" Output: "" Explanation: "leetcode" has only characters so we cannot separate them by digits.
Example 3:
Input: s = "1229857369" Output: "" Explanation: "1229857369" has only digits so we cannot separate them by characters.
Constraints:
1 <= s.length <= 500sconsists of only lowercase English letters and/or digits.
Approach Overview
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.
Approach 1: Interleaving Lists Approach
In this approach, first, separate the input string s into two lists: one for letters and another for digits. If the difference in size between these two lists is more than 1, return an empty string, as reformatting is impossible. Otherwise, interleave the two lists to construct the output string. Start with the list that has more elements.
This C implementation uses arrays to separate letters and digits. It checks if the difference in count between letters and digits exceeds 1, returning an empty string if it does. It then populates the result by interleaving both arrays. Memory for the result string is dynamically allocated.
Complexity
Time complexity: O(n), where n is the length of the input string. Space complexity: O(n), due to storing characters in separate arrays.
Approach 2: Two Pointer Approach
This approach uses a single iteration with two pointers. The algorithm enhances handling of alternating character types and directly builds the output without separate lists. By traversing once with two pointers, it efficiently intersperses characters while iterating.
The C version executes a single pass through the input string with a pointer. It immediately places characters into the result if they alternate type. This reduces additional space usage compared to explicitly separating and storing characters.
Complexity
Time complexity: O(n). Space complexity: O(n), because of the result array in memory.
Approach 3: Simulation
We classify all characters in string s into two categories: "digits" and "letters", and put them into arrays a and b respectively.
Compare the lengths of a and b. If the length of a is less than b, swap a and b. Then check the difference in lengths; if it exceeds 1, return an empty string.
Next, iterate through both arrays simultaneously, appending characters from a and b alternately to the answer. After the iteration, if a is longer than b, append the last character of a to the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the length of string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Interleaving Lists Approach | Time complexity: O(n), where n is the length of the input string. Space complexity: O(n), due to storing characters in separate arrays. |
| Two Pointer Approach | Time complexity: O(n). Space complexity: O(n), because of the result array in memory. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Interleaving Lists Approach | O(n) | O(n) | Best for clarity and interviews where readability and correctness matter more than memory usage |
| Two Pointer Approach | O(n) | O(1) | Useful when optimizing space or demonstrating in-place string/array manipulation |
Video Solution
Reformat The String| Leetcode 1417| Leetcode Weekly 185| Java| Hindi • Pepcoding • 1,745 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Reformat The String easy or hard?
Reformat The String Python/Java solution
How to solve Reformat The String in O(n)?
What is the best approach for Reformat The String?
Is Reformat The String asked at Google/Amazon/Meta?
What data structure is used in Reformat The String?
What is the time complexity of Reformat The String?
Ready to solve this problem?
Practice Reformat The String with our built-in code editor and test cases.
Practice on FleetCode