Reformat The String solution and explanation
7 more videos on this problem
Reformat The String| Leetcode 1417| Leetcode Weekly 185| Java| HindiPepcoding · 21:57 · 1K views
Reformat The String || Weekly Contest 185 || leetcode 1417. || c++ solutioncode Explainer · 6:48 · 696 views
Reformat The String (Leetcode 1417)Coding Interviews · 11:39 · 683 views
Vol22 - Leetcode - Problem 1417 - Reformat the string - Golang - Phỏng vấn - Thuật toánYuh lập trình viên · 15:31 · 343 views
LeetCode 1417 - Reformat The String: A Microsoft JourneyThe Lofi Dev · 11:42 · 225 views
Reformat the String | Modify the strings accordingly| Programming | Placements | Leetcode |InterviewProgramming World · 41:45 · 205 views
LEETCODE - 1417. Reformat The String #3Samed Haa · 16:30 · 127 views
LeetCode 1417: Reformat The StringAlitaCode · 29:01 · 2 views
The problem
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.
def reformat(s: str) -> str:
letters = []
digits = []
for char in s:
if char.isalpha():
letters.append(char)
else:
digits.append(char)
if abs(len(letters) - len(digits)) > 1:
return ""
result = []
letter_flag = len(letters) > len(digits)
while letters and digits:
if letter_flag:
result.append(letters.pop())
else:
result.append(digits.pop())
letter_flag = not letter_flag
result.extend(letters or digits)
return ''.join(result)import java.util.*;
public class ReformatString {
public String reformat(String s) {
List<Character> letters = new ArrayList<>();
List<Character> digits = new ArrayList<>();
for (char c : s.toCharArray()) {
if (Character.isLetter(c))
letters.add(c);
else
digits.add(c);
}
if (Math.abs(letters.size() - digits.size()) > 1)
return "";
StringBuilder result = new StringBuilder();
boolean letterFlag = letters.size() > digits.size();
Iterator<Character> it1 = letters.iterator();
Iterator<Character> it2 = digits.iterator();
while (it1.hasNext() && it2.hasNext()) {
if (letterFlag)
result.append(it1.next());
else
result.append(it2.next());
letterFlag = !letterFlag;
}
while (it1.hasNext()) result.append(it1.next());
while (it2.hasNext()) result.append(it2.next());
return result.toString();
}
}#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <cmath>
using namespace std;
string reformat(string s) {
vector<char> letters, digits;
for (char c : s) {
if (isalpha(c))
letters.push_back(c);
else if (isdigit(c))
digits.push_back(c);
}
if (abs((int)letters.size() - (int)digits.size()) > 1)
return "";
string result;
bool letterFlag = letters.size() > digits.size();
auto it1 = letters.begin(), it2 = digits.begin();
while (it1 != letters.end() && it2 != digits.end()) {
if (letterFlag)
result += *it1++;
else
result += *it2++;
letterFlag = !letterFlag;
}
while (it1 != letters.end()) result += *it1++;
while (it2 != digits.end()) result += *it2++;
return result;
}function reformat(s) {
let letters = [];
let digits = [];
for (let char of s) {
if (isNaN(char))
letters.push(char);
else
digits.push(char);
}
if (Math.abs(letters.length - digits.length) > 1)
return "";
let result = [];
let i = 0, j = 0;
let letterFlag = letters.length > digits.length;
while (i < letters.length && j < digits.length) {
if (letterFlag)
result.push(letters[i++]);
else
result.push(digits[j++]);
letterFlag = !letterFlag;
}
result = result.concat(letters.slice(i)).concat(digits.slice(j));
return result.join('');
}#include <stdio.h>
#include <string.h>
#include <ctype.h>
char* reformat(char* s) {
int n = strlen(s);
char letters[n];
char digits[n];
int l = 0, d = 0;
for (int i = 0; i < n; i++) {
if (isalpha(s[i]))
letters[l++] = s[i];
else if (isdigit(s[i]))
digits[d++] = s[i];
}
if (abs(l - d) > 1) return "";
char *result = malloc((n + 1) * sizeof(char));
result[n] = '\0';
int i = 0, j = 0, k = 0;
while (i < l && j < d) {
result[k++] = (l > d) ? letters[i++] : digits[j++];
result[k++] = (l > d) ? digits[j++] : letters[i++];
}
while (i < l) result[k++] = letters[i++];
while (j < d) result[k++] = digits[j++];
return result;
}using System;
using System.Collections.Generic;
using System.Text;
class ReformatString {
public string Reformat(string s) {
List<char> letters = new List<char>();
List<char> digits = new List<char>();
foreach (char c in s) {
if (char.IsLetter(c))
letters.Add(c);
else if (char.IsDigit(c))
digits.Add(c);
}
if (Math.Abs(letters.Count - digits.Count) > 1)
return "";
StringBuilder result = new StringBuilder();
bool letterFlag = letters.Count > digits.Count;
int i = 0, j = 0;
while (i < letters.Count && j < digits.Count) {
if (letterFlag)
result.Append(letters[i++]);
else
result.Append(digits[j++]);
letterFlag = !letterFlag;
}
while (i < letters.Count) result.Append(letters[i++]);
while (j < digits.Count) result.Append(digits[j++]);
return result.ToString();
}
}The Python solution uses lists to separate letters and digits. If the lengths allow, it alternates elements into the result list, converting back to a string at the end. The interleaving depends on which list is larger.
Time complexity: O(n), as the input is processed and results are compiled. Space complexity: O(n), for storing separated characters.
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.
def reformat(s):
result, i = [], 0
while i < len(s):
if (not result or result[-1].isalpha() != s[i].isalpha()):
result.append(s[i])
i += 1
if len(result) < len(s):
return ""
return ''.join(result)public class ReformatString {
public String reformat(String s) {
StringBuilder result = new StringBuilder(s.length());
int i = 0, j = 0;
while (j < s.length()) {
char current = s.charAt(j);
if (Character.isLetter(current) && (result.length() == 0 || !Character.isLetter(result.charAt(result.length() - 1))))
result.append(current);
else if (Character.isDigit(current) && (result.length() == 0 || !Character.isDigit(result.charAt(result.length() - 1))))
result.append(current);
else
j++;
}
if (result.length() < s.length())
return "";
return result.toString();
}
}#include <iostream>
#include <string>
using namespace std;
string reformat(string s) {
string result(s.size(), '\0');
int i = 0, j = 0, l = 0;
while (j < s.size()) {
if (isalpha(s[j]) && (l == 0 || !isalpha(result[l - 1])))
result[l++] = s[j++];
else if (isdigit(s[j]) && (l == 0 || !isdigit(result[l - 1])))
result[l++] = s[j++];
else
j++;
}
if (l < s.size())
return "";
return result.substr(0, l);
}function reformat(s) {
let result = [];
let i = 0;
while (i < s.length) {
if (result.length === 0 || isNaN(result[result.length - 1]) !== isNaN(s[i]))
result.push(s[i]);
i++;
}
if (result.length < s.length)
return "";
return result.join('');
}#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
char* reformat(char* s) {
int n = strlen(s);
char* result = (char*)malloc(n + 1);
int i = 0, j = 0, l = 0;
while (j < n) {
if (isalpha(s[j]) && (l == 0 || !isalpha(result[l-1])))
result[l++] = s[j++];
else if (isdigit(s[j]) && (l == 0 || !isdigit(result[l-1])))
result[l++] = s[j++];
else
j++;
}
if (l < n)
return "";
result[l] = '\0';
return result;
}using System.Text;
class Solution {
public string Reformat(string s) {
StringBuilder result = new StringBuilder(s.Length);
int index = 0;
while (index < s.Length) {
if (result.Length == 0 || char.IsLetter(result[result.Length - 1]) != char.IsLetter(s[index]))
result.Append(s[index]);
index++;
}
if (result.Length < s.Length)
return "";
return result.ToString();
}
}The Python implementation builds the solution through a simple single-pass check, adjusting the character processing based on adjacent types. It avoids preliminary excessive list forming, aiming for tighter space utilization.
Time complexity: O(n). Space complexity: O(n), for the generated result list converted to a string.
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.
function reformat(s: string): string {
let a: string[] = [];
let b: string[] = [];
for (const c of s) {
if (c >= 'a' && c <= 'z') a.push(c);
else if (c >= '0' && c <= '9') b.push(c);
}
if (Math.abs(a.length - b.length) > 1) {
return '';
}
if (a.length < b.length) {
[a, b] = [b, a];
}
const ans: string[] = [];
for (let i = 0; i < b.length; i++) {
ans.push(a[i] + b[i]);
}
if (a.length > b.length) {
ans.push(a[a.length - 1]);
}
return ans.join('');
}func reformat(s string) string {
a := []byte{}
b := []byte{}
for _, c := range s {
if unicode.IsLetter(c) {
a = append(a, byte(c))
} else {
b = append(b, byte(c))
}
}
if len(a) < len(b) {
a, b = b, a
}
if len(a)-len(b) > 1 {
return ""
}
var ans strings.Builder
for i := range b {
ans.WriteByte(a[i])
ans.WriteByte(b[i])
}
if len(a) > len(b) {
ans.WriteByte(a[len(a)-1])
}
return ans.String()
}impl Solution {
pub fn reformat(s: String) -> String {
let mut a: Vec<char> = Vec::new();
let mut b: Vec<char> = Vec::new();
for c in s.chars() {
if c.is_ascii_lowercase() {
a.push(c);
} else if c.is_ascii_digit() {
b.push(c);
}
}
if (a.len() as i32 - b.len() as i32).abs() > 1 {
return String::new();
}
if a.len() < b.len() {
std::mem::swap(&mut a, &mut b);
}
let mut ans = String::new();
for i in 0..b.len() {
ans.push(a[i]);
ans.push(b[i]);
}
if a.len() > b.len() {
ans.push(a[a.len() - 1]);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Interleaving Lists Approach | Time complexity: O(n), as the input is processed and results are compiled. Space complexity: O(n), for storing separated characters. |
| Two Pointer Approach | Time complexity: O(n). Space complexity: O(n), for the generated result list converted to a string. |
| Simulation | – |
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 |
Frequently asked questions
Is Reformat The String easy or hard?
Reformat The String is classified as an Easy problem. The challenge lies mainly in handling edge cases such as unequal counts and deciding which character type should start the alternating sequence.
Reformat The String Python/Java solution
Python and Java implementations typically follow the same structure: iterate through the string, separate digits and letters into lists, then build the final alternating string. Both languages achieve O(n) time complexity with simple loops and string builders.
How to solve Reformat The String in O(n)?
First count digits and letters while scanning the string. If their count difference is greater than one, return an empty string. Otherwise alternate characters by either interleaving two lists or swapping characters into correct positions using two pointers. Both strategies complete in linear time.
What is the best approach for Reformat The String?
The interleaving lists approach is the most straightforward solution. Separate digits and letters into two arrays, then merge them alternately starting with the group that has more characters. This runs in O(n) time and O(n) space and is easy to implement correctly in interviews.
Is Reformat The String asked at Google/Amazon/Meta?
Reformat The String represents a common string manipulation pattern seen in technical interviews at companies like Amazon, Google, and Meta. The problem tests counting logic, conditional construction, and clean handling of edge cases in linear time.
What data structure is used in Reformat The String?
Most solutions use arrays or lists to store digits and letters separately before merging them. The optimized version uses a character array and two pointers to place characters directly at alternating indices without extra storage.
What is the time complexity of Reformat The String?
The optimal time complexity is O(n), where n is the length of the string. You scan the string once to classify characters and once more to build the alternating result. Space complexity ranges from O(n) with auxiliary lists to O(1) when using an in-place two pointer approach.