Scale Engineer

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.

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();    }}

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.

Solutions

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();  }}

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 →

Next problem