Reformat Phone Number solution and explanation
9 more videos on this problem
Reformat Phone Number | Leetcode 1694 | Leetcode SolutionEasyLeetcode · 10:12 · 1K views
1694. Reformat Phone Number (Leetcode Easy)Programming Live with Larry · 7:21 · 708 views
LeetCode 1694 - Reformat Phone Number: A Microsoft JourneyThe Lofi Dev · 16:38 · 173 views
LeetCode 1694 Reformat Phone Number - Java Solution Using LinkedList & StringBuilderAlgorithmicIQ · 12:21 · 153 views
algorithm leetcode 1694 Reformat Phone NumberRoy Son · 3:55 · 123 views
Reformat Phone Number | Leetcode | Java | Solution | ExplanationCodingWithTricks · 7:45 · 43 views
LeetCode 1694: Reformat Phone Number | Easy String Manipulation Solution Explained!Ahmet Koylan · 5:06 · 40 views
1694. Reformat Phone Number - Javascript - Time: O(n) Space: O(n) - LeetcodeAaron Sadino Coding · 40:38 · 32 views
LeetCode 1694 | First Attempt & Narration | Reformat Phone NumberDLG_Coding · 58:30 · 23 views
leetcode | 1694. Reformat Phone Number | python practice | easyADevOpsEngineer · 9:22 · 19 views
The problem
You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.
You would like to reformat the phone number in a certain manner. Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits. The final digits are then grouped as follows:
- 2 digits: A single block of length 2.
- 3 digits: A single block of length 3.
- 4 digits: Two blocks of length 2 each.
The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.
Return the phone number after formatting.
Example 1:
Input: number = "1-23-45 6" Output: "123-456" Explanation: The digits are "123456". Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123". Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456". Joining the blocks gives "123-456".
Example 2:
Input: number = "123 4-567" Output: "123-45-67" Explanation: The digits are "1234567". Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123". Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45" and "67". Joining the blocks gives "123-45-67".
Example 3:
Input: number = "123 4-5678" Output: "123-456-78" Explanation: The digits are "12345678". Step 1: The 1st block is "123". Step 2: The 2nd block is "456". Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78". Joining the blocks gives "123-456-78".
Constraints:
2 <= number.length <= 100numberconsists of digits and the characters'-'and' '.- There are at least two digits in
number.
Approach overview
Problem Overview: You receive a phone number string containing digits, spaces, and dashes. The task is to remove separators and regroup the digits so that blocks are mostly of length three, with the last blocks adjusted to avoid a single digit group. The final format must contain groups separated by dashes.
Approach 1: Greedy Grouping (Time: O(n), Space: O(n))
This approach first filters the input to keep only numeric characters. You iterate through the string and append digits to a clean buffer. Once you have the raw digit sequence, grouping is performed greedily: take blocks of three digits while possible. The only exception happens near the end. If exactly four digits remain, split them into two groups of two instead of creating a 3-1 pattern. This rule guarantees that no block has length one.
The key insight is that a phone number formatted with groups of three is optimal for most of the string. Only the final 2–4 digits require special handling. Implementations usually use a loop that processes digits while checking how many remain. When four digits remain, output 2-2 groups instead of 3-1. Because each digit is processed once, the algorithm runs in linear time with O(n) space for the result string.
This solution relies purely on sequential iteration and simple conditional checks. The logic fits naturally within string processing problems and is often categorized under greedy algorithms because each step locally chooses the largest valid group size.
Approach 2: Regular Expressions and String Manipulation (Time: O(n), Space: O(n))
This version also begins by stripping non-digit characters from the input. Instead of manually managing indices, you rely on pattern-based transformations. After extracting digits, logic determines the correct grouping for the tail (2, 3, or 4 digits remaining). Regex can then split the prefix into groups of three using patterns like .{3}, while the remaining digits are appended according to the special-case rules.
The benefit is concise code in languages with strong regex support such as Python or JavaScript. However, under the hood the algorithm still performs a linear scan and substring operations. Complexity remains O(n) time and O(n) space due to intermediate strings.
Regex-based solutions trade explicit control for readability. They are useful when your language provides expressive pattern matching, though most interviewers expect the direct greedy implementation since it shows clear reasoning about the grouping constraints.
Recommended for interviews: The greedy grouping approach is the expected solution. It demonstrates that you understand the constraint preventing single-digit groups and can handle edge cases like four remaining digits. Mentioning the regex alternative shows familiarity with language tooling, but the greedy method communicates stronger algorithmic clarity.
Approach 1: Greedy Grouping
This approach involves removing all spaces and dashes to leave only the digits. Then, greedily group these digits into blocks of size 3. If there are 4 or fewer digits left after grouping, handle them according to the specified rules (4 digits as two blocks of 2, 3 as a single block of 3, and 2 as a single block of 2).
def reformatNumber(number: str) -> str:
digits = ''.join(ch for ch in number if ch.isdigit())
n = len(digits)
result = []
i = 0
# Greedily group
while i < n:
if (n - i) > 4:
result.append(digits[i:i+3])
i += 3
else:
if (n - i) == 4:
result.append(digits[i:i+2])
result.append(digits[i+2:i+4])
else:
result.append(digits[i:])
break
return '-'.join(result)public class Solution {
public String reformatNumber(String number) {
StringBuilder digits = new StringBuilder();
// Collect digits
for (char ch : number.toCharArray()) {
if (Character.isDigit(ch)) {
digits.append(ch);
}
}
StringBuilder result = new StringBuilder();
int n = digits.length();
int i = 0;
// Formatting
while (i < n) {
if ((n - i) > 4) {
result.append(digits.substring(i, i + 3)).append("-");
i += 3;
} else {
if (n - i == 4) {
result.append(digits.substring(i, i + 2)).append("-").append(digits.substring(i + 2, i + 4));
} else {
result.append(digits.substring(i));
}
break;
}
}
return result.toString();
}
}#include <iostream>
#include <string>
using namespace std;
string reformatNumber(string number) {
string digits = "";
// Extract all digits
for (char ch : number) {
if (isdigit(ch))
digits += ch;
}
string result = "";
int n = digits.size();
int i = 0;
// Reformat
while (i < n) {
if ((n - i) > 4) {
result += digits.substr(i, 3) + "-";
i += 3;
} else {
if (n - i == 4) {
result += digits.substr(i, 2) + "-" + digits.substr(i + 2, 2);
} else {
result += digits.substr(i);
}
break;
}
}
return result;
}function reformatNumber(number) {
let digits = '';
for (let char of number) {
if (!isNaN(char) && char !== ' ') {
digits += char;
}
}
const len = digits.length;
let result = [];
let i = 0;
while (i < len) {
if (len - i > 4) {
result.push(digits.substring(i, i + 3));
i += 3;
} else {
if (len - i === 4) {
result.push(digits.substring(i, i + 2));
result.push(digits.substring(i + 2, i + 4));
} else {
result.push(digits.substring(i));
}
break;
}
}
return result.join('-');
}#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* reformatNumber(char* number) {
int length = strlen(number);
char* digits = (char*)malloc(length + 1);
int index = 0;
// Extract digits
for (int i = 0; i < length; ++i) {
if (number[i] >= '0' && number[i] <= '9') {
digits[index++] = number[i];
}
}
digits[index] = '\0';
int n = index;
char* result = (char*)malloc((n * 2) * sizeof(char)); // Overestimation
index = 0;
// Greedily group digits as required
for (int i = 0; i < n;) {
if (n - i > 4) {
// Group of 3
result[index++] = digits[i++];
result[index++] = digits[i++];
result[index++] = digits[i++];
result[index++] = '-';
} else {
if (n - i == 4) {
result[index++] = digits[i++];
result[index++] = digits[i++];
result[index++] = '-';
result[index++] = digits[i++];
result[index++] = digits[i++];
} else {
// either 3 or 2
while (i < n) {
result[index++] = digits[i++];
}
}
break;
}
}
if (result[index - 1] == '-') {
index--; // Remove trailing dash
}
result[index] = '\0';
free(digits);
return result;
}public class Solution {
public string ReformatNumber(string number) {
var digits = new StringBuilder();
foreach (char ch in number) {
if (char.IsDigit(ch)) {
digits.Append(ch);
}
}
var result = new List<string>();
int index = 0;
int len = digits.Length;
while (index < len) {
if ((len - index) > 4) {
result.Add(digits.ToString(index, 3));
index += 3;
} else {
if ((len - index) == 4) {
result.Add(digits.ToString(index, 2));
result.Add(digits.ToString(index + 2, 2));
} else {
result.Add(digits.ToString(index));
}
break;
}
}
return string.Join("-", result);
}
}The Python solution employs list comprehension to gather digits from the input number, and a greedy approach to form groups of digits according to the conditions given: the remaining digits if there are fewer than 5, are handled distinctly as per the rules.
Time Complexity: O(n), considering the creation of a filtered digit list and the formation of the reformatted string.
Space Complexity: O(n), primarily for the digit storage and aggregation during processing.
Approach 2: Using Regular Expressions and String Manipulation
First, clean the input string using regular expressions to extract all digits. Then manage the resultant string to construct groups based on the count of remaining digits. Specifically, handle cases with fewer than 5 digits appropriately while using regex or string operations for efficient manipulation and transformations.
import re
def reformatNumber(number: str) -> str:
digits = re.sub(r'[\s-]', '', number)
groups = []
i = 0
n = len(digits)
while i < n:
if n - i > 4:
groups.append(digits[i:i+3])
i += 3
else:
if n - i == 4:
groups.append(digits[i:i+2])
groups.append(digits[i+2:i+4])
else:
groups.append(digits[i:])
break
return '-'.join(groups)function reformatNumber(number) {
let digits = number.replace(/[\s-]/g, '');
let len = digits.length;
let result = [];
let i = 0;
while (i < len) {
if (len - i > 4) {
result.push(digits.substring(i, i + 3));
i += 3;
} else {
if (len - i === 4) {
result.push(digits.substring(i, i + 2));
result.push(digits.substring(i + 2, i + 4));
} else {
result.push(digits.substring(i));
}
break;
}
}
return result.join('-');
}This Python solution uses a regular expression to strip non-digit characters from the input. Afterward, we visually segment the digits per the rules, paying special heed to cases where digit chunks end in fewer than five entities, to assure no block of size one occurs.
Time Complexity: O(n), for filtering and reformulation activities.
Space Complexity: O(n), accountable to the digit extraction storage and grouping lists.
Approach 3: Simple Simulation
First, according to the problem description, we remove all spaces and hyphens from the string.
Let the current string length be n. Then we traverse the string from the beginning, grouping every 3 characters together and adding them to the result string. We take a total of n / 3 groups.
If there is 1 character left in the end, we form a new group of two characters with the last character of the last group and this character, and add it to the result string. If there are 2 characters left, we directly form a new group with these two characters and add it to the result string.
Finally, we add hyphens between all groups and return the result string.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
function reformatNumber(number: string): string {
const cs = [...number].filter(c => c !== ' ' && c !== '-');
const n = cs.length;
return cs
.map((v, i) => {
if (((i + 1) % 3 === 0 && i < n - 2) || (n % 3 === 1 && n - 3 === i)) {
return v + '-';
}
return v;
})
.join('');
}func reformatNumber(number string) string {
number = strings.ReplaceAll(number, " ", "")
number = strings.ReplaceAll(number, "-", "")
n := len(number)
ans := []string{}
for i := 0; i < n/3; i++ {
ans = append(ans, number[i*3:i*3+3])
}
if n%3 == 1 {
ans[len(ans)-1] = ans[len(ans)-1][:2]
ans = append(ans, number[n-2:])
} else if n%3 == 2 {
ans = append(ans, number[n-2:])
}
return strings.Join(ans, "-")
}impl Solution {
pub fn reformat_number(number: String) -> String {
let cs: Vec<char> = number.chars().filter(|&c| c != ' ' && c != '-').collect();
let n = cs.len();
cs.iter()
.enumerate()
.map(|(i, c)| {
if ((i + 1) % 3 == 0 && i < n - 2) || (n % 3 == 1 && i == n - 3) {
return c.to_string() + &"-";
}
c.to_string()
})
.collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Grouping | Time Complexity: O(n), considering the creation of a filtered digit list and the formation of the reformatted string. |
| Using Regular Expressions and String Manipulation | Time Complexity: O(n), for filtering and reformulation activities. |
| Simple Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Grouping | O(n) | O(n) | General solution for interviews; explicit control over grouping logic |
| Regex + String Manipulation | O(n) | O(n) | Useful in scripting languages where regex simplifies formatting logic |
Frequently asked questions
Is Reformat Phone Number easy or hard?
Reformat Phone Number is classified as an Easy problem on LeetCode with an acceptance rate around 67%. The main challenge is handling the edge case where four digits remain so that the output avoids a single-digit group.
Reformat Phone Number Python/Java solution
Both Python and Java implementations follow the same idea: strip non-digit characters, iterate through digits, and build groups using conditional checks on the remaining length. Python often uses list joins for efficiency, while Java typically uses a StringBuilder.
How to solve Reformat Phone Number in O(n)?
First iterate through the input and collect only numeric characters. Then process the digit string greedily: append groups of three digits separated by dashes until the remaining digits are 2–4. If four digits remain, split them into 2-2 groups; otherwise keep the remaining group as size 2 or 3. Each digit is processed once, giving O(n) complexity.
What is the best approach for Reformat Phone Number?
The greedy grouping approach is the best solution. First remove spaces and dashes to extract only digits, then form groups of three while possible. If four digits remain, split them into two groups of two to avoid a single-digit block. This runs in O(n) time and O(n) space.
Is Reformat Phone Number asked at Google/Amazon/Meta?
Problems like Reformat Phone Number appear in interviews focused on string manipulation and formatting logic. Variants of string grouping and formatting have shown up in coding rounds at companies such as Amazon and Google, especially for entry-level and screening interviews.
What data structure is used in Reformat Phone Number?
The solution primarily uses string processing with a dynamic buffer or string builder. You store digits in a temporary string or array, then append grouped segments to the result. No complex data structures are required beyond basic string manipulation.
What is the time complexity of Reformat Phone Number?
The optimal solution runs in O(n) time where n is the length of the input string. You scan the string once to collect digits and once more to create formatted groups. Space complexity is O(n) for storing the cleaned digits and final formatted output.