Reformat Phone Number - Solution & Explanation

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.