# Reformat The String
**Difficulty:** EASY
[External](https://leetcode.com/problems/reformat-the-string)
Canonical: https://scaleengineer.com/dsa/problems/reformat-the-string
**Data structures:** String
---
## 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 <= 500`
* `s` consists of only lowercase English letters and/or digits.

# Approaches
## Separate into Lists and Interleave
This intuitive approach involves segregating the characters of the input string into two distinct collections: one for letters and one for digits. After separation, it validates the possibility of a reformatted string by checking if the counts of letters and digits differ by more than one. If a valid arrangement is possible, it constructs the final string by interleaving elements from the two collections, ensuring the larger collection's elements appear first.
**Time:** O(N), where N is the length of `s`. The first loop takes O(N) to separate characters. The second loop takes O(N) to build the string. · **Space:** O(N), where N is the length of the string. The `letters` and `digits` lists together store all N characters. The `StringBuilder` also requires O(N) space for the result.
**Pros:** Straightforward logic that is easy to implement and understand.; Clearly separates the concerns of parsing and building.
**Cons:** Uses extra space for the intermediate lists, making it less memory-efficient than possible.
### Explanation
This method first separates all characters into a list of letters and a list of digits. This requires a single pass through the input string. Once separated, it's easy to check the condition for a possible reformatting: the difference in the number of letters and digits must not be more than 1. If this condition fails, we immediately know no solution exists. Otherwise, we can construct the result. We use a `StringBuilder` for efficient string construction. We identify which group of characters is larger (or if they're equal) and start the interleaving process with a character from that larger group. We append characters one by one, alternating between the two lists, until the shorter list is exhausted. If there's one character left in the longer list, we append it at the end.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    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);
            }
        }

        int letterCount = letters.size();
        int digitCount = digits.size();

        if (Math.abs(letterCount - digitCount) > 1) {
            return "";
        }

        StringBuilder result = new StringBuilder();
        List<Character> primary = letterCount >= digitCount ? letters : digits;
        List<Character> secondary = letterCount < digitCount ? letters : digits;

        for (int i = 0; i < secondary.size(); i++) {
            result.append(primary.get(i));
            result.append(secondary.get(i));
        }

        if (primary.size() > secondary.size()) {
            result.append(primary.get(primary.size() - 1));
        }

        return result.toString();
    }
}
```
### Algorithm
- Initialize two empty lists, `letters` and `digits`.
- Iterate through each character of the input string `s`.
- If the character is a letter, add it to the `letters` list.
- If the character is a digit, add it to the `digits` list.
- After the loop, check if the absolute difference between the size of `letters` and `digits` is greater than 1. If it is, return an empty string `""`.
- Initialize a `StringBuilder` to build the result.
- Identify which list is longer (primary) and which is shorter (secondary). If they are of equal length, the choice is arbitrary.
- Iterate from `i = 0` to the size of the shorter list, appending one character from the primary list and one from the secondary list to the `StringBuilder`.
- If the lists have different lengths, append the last remaining character from the longer list.
- Convert the `StringBuilder` to a string and return it.

## Two Pointers with Direct Placement
A more space-efficient approach that avoids creating intermediate data structures for letters and digits. It begins with a single pass to count the character types and validate if a solution is possible. If it is, a result character array is allocated. Then, in a second pass over the input string, it uses two index pointers to place each letter and digit directly into its correct, alternating position in the result array. This method builds the final string more directly.
**Time:** O(N). The algorithm makes two full passes over the string, one for counting and one for building the result. This is linear time. · **Space:** O(N). The primary space usage is the `result` character array, which is required for the output. This approach avoids the extra O(N) space for intermediate lists used in the first approach.
**Pros:** More memory-efficient as it avoids intermediate lists.; Maintains optimal O(N) time complexity.
**Cons:** Requires two passes over the input string, though this doesn't change the overall time complexity class.
### Explanation
This optimized approach improves on space usage. Instead of storing characters in separate lists, it first performs a preliminary pass just to count the letters and digits. This count is used to check the validity condition (`abs(letterCount - digitCount) <= 1`) and to determine which character type should occupy the even indices of the result string (the more numerous type). After this, a character array for the result is created. A second pass over the input string is then performed. During this pass, each character is placed directly into its final position in the result array using two pointers that keep track of the next available even and odd indices. For example, if letters are more numerous, one pointer `letterIdx` starts at 0 and increments by 2, while `digitIdx` starts at 1 and also increments by 2. This avoids the overhead of intermediate list storage.

```java
class Solution {
    public String reformat(String s) {
        int n = s.length();
        int letterCount = 0;
        int digitCount = 0;
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                letterCount++;
            } else {
                digitCount++;
            }
        }

        if (Math.abs(letterCount - digitCount) > 1) {
            return "";
        }

        char[] result = new char[n];
        int letterIdx = letterCount >= digitCount ? 0 : 1;
        int digitIdx = letterCount < digitCount ? 0 : 1;

        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                result[letterIdx] = c;
                letterIdx += 2;
            } else {
                result[digitIdx] = c;
                digitIdx += 2;
            }
        }

        return new String(result);
    }
}
```
### Algorithm
- First, iterate through the string `s` to count the number of letters (`letterCount`) and digits (`digitCount`).
- Check the validity condition: if `abs(letterCount - digitCount) > 1`, return `""`.
- Create a character array `result` of length `s.length()`.
- Initialize two index pointers: `letterIdx` for the next letter position and `digitIdx` for the next digit position.
- Determine the starting indices. If `letterCount` is greater than or equal to `digitCount`, letters start at index 0 and digits at index 1. Otherwise, digits start at 0 and letters at 1.
- Iterate through the input string `s` again.
- When a letter is found, place it at `result[letterIdx]` and increment `letterIdx` by 2.
- When a digit is found, place it at `result[digitIdx]` and increment `digitIdx` by 2.
- Finally, convert the `result` character array into a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String reformat(String s) {
    StringBuilder a = new StringBuilder();
    StringBuilder b = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (Character.isDigit(c)) {
        a.append(c);
      } else {
        b.append(c);
      }
    }
    int m = a.length(), n = b.length();
    if (Math.abs(m - n) > 1) {
      return "";
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < Math.min(m, n); ++i) {
      if (m > n) {
        ans.append(a.charAt(i));
        ans.append(b.charAt(i));
      } else {
        ans.append(b.charAt(i));
        ans.append(a.charAt(i));
      }
    }
    if (m > n) {
      ans.append(a.charAt(m - 1));
    }
    if (m < n) {
      ans.append(b.charAt(n - 1));
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string reformat(string s) {
    string a = "", b = "";
    for (char c : s) {
      if (isdigit(c))
        a += c;
      else
        b += c;
    }
    int m = a.size(), n = b.size();
    if (abs(m - n) > 1)
      return "";
    string ans = "";
    for (int i = 0; i < min(m, n); ++i) {
      if (m > n) {
        ans += a[i];
        ans += b[i];
      } else {
        ans += b[i];
        ans += a[i];
      }
    }
    if (m > n)
      ans += a[m - 1];
    if (m < n)
      ans += b[n - 1];
    return ans;
  }
};

```

### Python

```python
class Solution:
    def reformat(self, s: str) -> str: a = [c for c in s if c . islower()] b = [c for c in s if c . isdigit()] if abs(len(a) - len(b)) > 1: return '' if len(a) < len(b): a, b = b, a ans = [] for x, y in zip(a, b): ans . append(x + y) if len(a) > len(b): ans . append(a[- 1]) return '' . join(ans)

```