Code Implementation

class Solution:
    def reformat(self, s: str) -> str:
        letters = [c for c in s if c.isalpha()]
        digits = [c for c in s if c.isdigit()]
        if abs(len(letters) - len(digits)) > 1:
            return ""
        res = []
        # Start with the longer group if uneven
        if len(letters) > len(digits):
            first, second = letters, digits
        else:
            first, second = digits, letters
        for i in range(len(s)):
            if i % 2 == 0:
                if first:
                    res.append(first.pop())
            else:
                if second:
                    res.append(second.pop())
        return ''.join(res)
      

class Solution {
public:
    string reformat(string s) {
        vector<char> letters, digits;
        for (char c : s) {
            if (isalpha(c)) letters.push_back(c);
            else if (isdigit(c)) digits.push_back(c);
        }
        if (abs((int)letters.size() - (int)digits.size()) > 1) return "";
        string res = "";
        bool letterFirst = letters.size() >= digits.size();
        int i = 0, j = 0;
        for (int k = 0; k < s.length(); ++k) {
            if ((k % 2 == 0) == letterFirst) {
                res += letters[i++];
            } else {
                res += digits[j++];
            }
        }
        return res;
    }
};
      

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 if (Character.isDigit(c)) digits.add(c);
        }
        if (Math.abs(letters.size() - digits.size()) > 1) return "";
        StringBuilder sb = new StringBuilder();
        boolean letterFirst = letters.size() >= digits.size();
        int i = 0, j = 0;
        for (int k = 0; k < s.length(); ++k) {
            if ((k % 2 == 0) == letterFirst) {
                sb.append(letters.get(i++));
            } else {
                sb.append(digits.get(j++));
            }
        }
        return sb.toString();
    }
}
      

var reformat = function(s) {
    let letters = [], digits = [];
    for (let c of s) {
        if (/[a-zA-Z]/.test(c)) letters.push(c);
        else if (/[0-9]/.test(c)) digits.push(c);
    }
    if (Math.abs(letters.length - digits.length) > 1) return "";
    let res = [];
    let letterFirst = letters.length >= digits.length;
    let i = 0, j = 0;
    for (let k = 0; k < s.length; ++k) {
        if ((k % 2 === 0) === letterFirst) {
            res.push(letters[i++]);
        } else {
            res.push(digits[j++]);
        }
    }
    return res.join('');
};
      

Problem Description

Given a string s consisting of lowercase English letters and digits, reformat it so that no two adjacent characters are of the same type (i.e., no two letters or two digits are next to each other). Return any possible reformatted string that meets this condition, or return an empty string if it is impossible.

• Each character from s must be used exactly once.
• There is at most one valid solution, and you cannot reuse or omit any character.
• If the difference in count between letters and digits is more than 1, it is impossible to create such a string.

Thought Process

The problem asks us to rearrange the string so that no two adjacent characters are both letters or both digits. A brute-force approach would be to try all possible permutations, but that is highly inefficient and unnecessary here. Instead, we can use the observation that the only way to alternate perfectly is if the counts of letters and digits are nearly equal (differ by at most 1).

Therefore, our first step is to count the number of letters and digits. If their counts differ by more than 1, it's impossible. Otherwise, we can alternate between the two types, starting with the type that has more characters. This way, we ensure no two adjacent characters are of the same type.

The problem becomes one of partitioning the string into two lists (letters and digits) and then merging them in alternating order.

Solution Approach

• Step 1: Separate Letters and Digits
  Go through each character in s and place letters in one list and digits in another.
• Step 2: Check for Possibility
  If the difference in lengths between letters and digits is greater than 1, return an empty string because alternating would be impossible.
• Step 3: Merge Alternately
  Decide which group (letters or digits) is larger. Start the result string with a character from the larger group and then alternate between the two groups until all characters are used.
• Step 4: Build the Result
  Use a loop to append characters from each group in turn, ensuring the alternation is maintained.
• Step 5: Return the Result
  Join the characters to form the reformatted string and return it.

This approach is efficient and direct, avoiding unnecessary computation.

Example Walkthrough

Consider the input s = "a0b1c2".

• Separate into letters: ['a', 'b', 'c'] and digits: ['0', '1', '2']
• Counts are equal (3 letters, 3 digits), so it is possible to alternate.
• Start with a letter (since counts are equal, either is fine):
• Build result: 'a' (letter), '0' (digit), 'b' (letter), '1' (digit), 'c' (letter), '2' (digit)
• Final result: "a0b1c2"
• Alternatively, starting with a digit: "0a1b2c" is also valid.

Notice how no two adjacent characters are of the same type, and all original characters are used exactly once.

Time and Space Complexity

• Brute-force Approach:
  Generating all permutations is O(n!), which is infeasible for even modest input sizes.
• Optimized Approach (used here):
  
  • Time Complexity: O(n), where n is the length of s. We make a single pass to separate characters and one more to build the result.
  • Space Complexity: O(n), as we store the separated lists and the result.

Summary

The key insight is that alternating letters and digits is only possible when their counts differ by at most one. By splitting the input into two lists and merging them in alternating order, we efficiently build a valid reformatted string or determine impossibility. This approach is both simple and optimal for the problem constraints.