# Reformat Phone Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/reformat-phone-number)
Canonical: https://scaleengineer.com/dsa/problems/reformat-phone-number
**Data structures:** String
**Companies:** [Activision](https://scaleengineer.com/companies/activision)
---
## 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 <= 100`
* `number` consists of digits and the characters `'-'` and `' '`.
* There are at least **two** digits in `number`.

# Approaches
## Brute Force with String Concatenation
This is a straightforward, brute-force approach that directly translates the problem's requirements into code. It first filters the input string to get only the digits and then formats this new string of digits. The main drawback is its use of repeated string concatenation in a loop, which is known to be inefficient in Java because strings are immutable. Each concatenation creates a new string object, leading to quadratic time complexity.
**Time:** O(L^2), where L is the length of the input string. If N is the number of digits, the filtering step is O(L * N) and the formatting step is O(N^2) because string concatenation in a loop takes time proportional to the lengths of the strings being joined. · **Space:** O(N), where N is the number of digits in the input. This space is used to store the `digitsOnly` string and the `result` string. Many more temporary strings are created but are garbage collected.
**Pros:** Simple to understand and implement.; The logic directly follows the problem description.
**Cons:** Highly inefficient in terms of time complexity due to the nature of string concatenation in Java.; Creates a large number of temporary, intermediate string objects, leading to increased work for the garbage collector.
### Explanation
The process is split into two phases. First, we build a new string containing only the digits from the input. We do this by iterating through the input and appending digits to a string variable. This is inefficient because each `+=` operation on a string creates a new string and copies the content of the old string and the new character.

Second, we build the final formatted string, again using string concatenation. We take blocks of three digits as long as more than four digits are left. The final 2, 3, or 4 digits are handled as a special case.

```java
class Solution {
    public String reformatNumber(String number) {
        // Step 1: Filter out non-digits using string concatenation
        String digitsOnly = "";
        for (char c : number.toCharArray()) {
            if (Character.isDigit(c)) {
                digitsOnly += c;
            }
        }

        // Step 2: Format the digits string using string concatenation
        String result = "";
        int n = digitsOnly.length();
        int i = 0;

        while (n - i > 4) {
            result += digitsOnly.substring(i, i + 3);
            result += "-";
            i += 3;
        }

        // Handle the last group of digits
        int remaining = n - i;
        if (remaining == 4) {
            result += digitsOnly.substring(i, i + 2);
            result += "-";
            result += digitsOnly.substring(i + 2, i + 4);
        } else { // remaining is 2 or 3
            result += digitsOnly.substring(i, n);
        }

        return result;
    }
}
```
### Algorithm
- Initialize an empty string `digitsOnly`.
- Iterate through each character of the input `number` string.
- If the character is a digit, append it to `digitsOnly` using the `+` operator (`digitsOnly += character`).
- After collecting all digits, initialize another empty string `result`.
- Use an index `i` to iterate through `digitsOnly`.
- While the number of remaining digits is more than 4, append a block of 3 digits to `result` followed by a dash, using the `+` operator. Increment the index `i` by 3.
- Once 4 or fewer digits remain, handle them based on the rules:
  - If 4 digits remain, append two blocks of 2, separated by a dash.
  - If 2 or 3 digits remain, append them as a single block.
- Return the final `result` string.

## Two-Pass with StringBuilder
This approach significantly improves performance by using `StringBuilder`, which is a mutable sequence of characters. Instead of creating new string objects on each append operation, `StringBuilder` modifies its internal character array, making appends an amortized constant-time operation. The overall logic remains a two-pass process: first, filter the digits, and second, construct the formatted output string.
**Time:** O(L), where L is the length of the input string. The filtering pass takes O(L) time. The formatting pass takes O(N) time, where N is the number of digits (N ≤ L). Thus, the total time complexity is linear. · **Space:** O(N), where N is the number of digits. This space is for the two `StringBuilder` objects that hold the digits and the final result.
**Pros:** Efficient time complexity, linear in the length of the input string.; Efficient memory usage by avoiding the creation of excessive temporary objects.; It is the idiomatic way to perform string manipulation in Java.
**Cons:** Requires two passes: one to filter the digits and another to format them.; Uses slightly more memory than an in-place solution might, due to holding two `StringBuilder` objects (though the overall space complexity remains the same).
### Explanation
This is the standard and most efficient way to solve this problem in Java. We first iterate through the input string once to collect all the digits into a `StringBuilder`. This is efficient as `StringBuilder.append()` is fast.

Then, we iterate through the collected digits to build the final formatted string in a second `StringBuilder`. The logic for grouping is the same as the brute-force approach, but the use of `StringBuilder` for construction avoids the quadratic time complexity of string concatenation.

```java
class Solution {
    public String reformatNumber(String number) {
        // Step 1: Filter out non-digits using StringBuilder
        StringBuilder digitsOnly = new StringBuilder();
        for (char c : number.toCharArray()) {
            if (Character.isDigit(c)) {
                digitsOnly.append(c);
            }
        }

        // Step 2: Format the digits using StringBuilder
        StringBuilder result = new StringBuilder();
        int n = digitsOnly.length();
        int i = 0;

        while (n - i > 4) {
            result.append(digitsOnly.substring(i, i + 3));
            result.append("-");
            i += 3;
        }

        // Handle the last group of digits
        int remaining = n - i;
        if (remaining == 4) {
            result.append(digitsOnly.substring(i, i + 2));
            result.append("-");
            result.append(digitsOnly.substring(i + 2, i + 4));
        } else { // remaining is 2 or 3
            result.append(digitsOnly.substring(i, n));
        }

        return result.toString();
    }
}
```
### Algorithm
- **Filter Pass:**
  - Create a `StringBuilder` called `digitsOnly`.
  - Iterate through the input `number` string. If a character is a digit, append it to `digitsOnly`.
- **Format Pass:**
  - Create a second `StringBuilder` called `result`.
  - Use an index `i` to track the position in `digitsOnly`.
  - Loop while the number of remaining digits (`digitsOnly.length() - i`) is greater than 4.
    - In each iteration, append a 3-digit block from `digitsOnly` to `result`, followed by a dash.
    - Increment `i` by 3.
  - After the loop, handle the final 2, 3, or 4 digits:
    - If 4 digits remain, append them as two 2-digit blocks separated by a dash.
    - If 2 or 3 digits remain, append them as a single block.
  - Convert the `result` `StringBuilder` to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String reformatNumber(String number) {
    number = number.replace("-", "").replace(" ", "");
    int n = number.length();
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < n / 3; ++i) {
      ans.add(number.substring(i * 3, i * 3 + 3));
    }
    if (n % 3 == 1) {
      ans.set(ans.size() - 1, ans.get(ans.size() - 1).substring(0, 2));
      ans.add(number.substring(n - 2));
    } else if (n % 3 == 2) {
      ans.add(number.substring(n - 2));
    }
    return String.join("-", ans);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reformatNumber(string number) {
    string s;
    for (char c : number) {
      if (c != ' ' && c != '-') {
        s.push_back(c);
      }
    }
    int n = s.size();
    vector<string> res;
    for (int i = 0; i < n / 3; ++i) {
      res.push_back(s.substr(i * 3, 3));
    }
    if (n % 3 == 1) {
      res.back() = res.back().substr(0, 2);
      res.push_back(s.substr(n - 2));
    } else if (n % 3 == 2) {
      res.push_back(s.substr(n - 2));
    }
    string ans;
    for (auto &v : res) {
      ans += v;
      ans += "-";
    }
    ans.pop_back();
    return ans;
  }
};

```

### Python

```python
class Solution:
    def reformatNumber(self, number: str) -> str: number = number . replace("-", ""). replace(" ", "") n = len(number) ans = [number[i * 3: i * 3 + 3] for i in range(n // 3)] if n % 3 == 1: ans[- 1] = ans[- 1][: 2] ans . append(number[- 2:]) elif n % 3 == 2: ans . append(number[- 2:]) return "-" . join(ans)

```