Reformat The String

Easy

#1311Time: 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.

Data structures

String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public String reformat(String s) {6        List<Character> letters = new ArrayList<>();7        List<Character> digits = new ArrayList<>();8 9        for (char c : s.toCharArray()) {10            if (Character.isLetter(c)) {11                letters.add(c);12            } else {13                digits.add(c);14            }15        }16 17        int letterCount = letters.size();18        int digitCount = digits.size();19 20        if (Math.abs(letterCount - digitCount) > 1) {21            return "";22        }23 24        StringBuilder result = new StringBuilder();25        List<Character> primary = letterCount >= digitCount ? letters : digits;26        List<Character> secondary = letterCount < digitCount ? letters : digits;27 28        for (int i = 0; i < secondary.size(); i++) {29            result.append(primary.get(i));30            result.append(secondary.get(i));31        }32 33        if (primary.size() > secondary.size()) {34            result.append(primary.get(primary.size() - 1));35        }36 37        return result.toString();38    }39}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public String reformat(String s) {3        int n = s.length();4        int letterCount = 0;5        int digitCount = 0;6        for (char c : s.toCharArray()) {7            if (Character.isLetter(c)) {8                letterCount++;9            } else {10                digitCount++;11            }12        }13 14        if (Math.abs(letterCount - digitCount) > 1) {15            return "";16        }17 18        char[] result = new char[n];19        int letterIdx = letterCount >= digitCount ? 0 : 1;20        int digitIdx = letterCount < digitCount ? 0 : 1;21 22        for (char c : s.toCharArray()) {23            if (Character.isLetter(c)) {24                result[letterIdx] = c;25                letterIdx += 2;26            } else {27                result[digitIdx] = c;28                digitIdx += 2;29            }30        }31 32        return new String(result);33    }34}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String reformat(String s) {4    StringBuilder a = new StringBuilder();5    StringBuilder b = new StringBuilder();6    for (char c : s.toCharArray()) {7      if (Character.isDigit(c)) {8        a.append(c);9      } else {10        b.append(c);11      }12    }13    int m = a.length(), n = b.length();14    if (Math.abs(m - n) > 1) {15      return "";16    }17    StringBuilder ans = new StringBuilder();18    for (int i = 0; i < Math.min(m, n); ++i) {19      if (m > n) {20        ans.append(a.charAt(i));21        ans.append(b.charAt(i));22      } else {23        ans.append(b.charAt(i));24        ans.append(a.charAt(i));25      }26    }27    if (m > n) {28      ans.append(a.charAt(m - 1));29    }30    if (m < n) {31      ans.append(b.charAt(n - 1));32    }33    return ans.toString();34  }35}

1class Solution {2public:3  string reformat(string s) {4    string a = "", b = "";5    for (char c : s) {6      if (isdigit(c))7        a += c;8      else9        b += c;10    }11    int m = a.size(), n = b.size();12    if (abs(m - n) > 1)13      return "";14    string ans = "";15    for (int i = 0; i < min(m, n); ++i) {16      if (m > n) {17        ans += a[i];18        ans += b[i];19      } else {20        ans += b[i];21        ans += a[i];22      }23    }24    if (m > n)25      ans += a[m - 1];26    if (m < n)27      ans += b[n - 1];28    return ans;29  }30};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem