Reformat The String

This problem can be solved by using a queue-based approach. The idea is to separate all the characters and digits from the given string and store them in separate queues. If the absolute difference between the number of characters and the number of digits is greater than 1, then it’s impossible to reformat the string according to the given conditions, and we return an empty string.

If the number of digits is greater than or equal to the number of characters, we start forming the reformatted string with a digit, and vice versa. We continue taking one character from each queue alternately until one of the queues is empty. If there are still elements left in the other queue, we append the remaining element to the reformatted string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

from collections import deque

class Solution:
    def reformat(self, s: str) -> str:
        chars = deque()
        digits = deque()

        # Separate the characters and digits
        for ch in s:
            if ch.isdigit():
                digits.append(ch)
            else:
                chars.append(ch)

        # If it's impossible to reformat the string
        if abs(len(chars) - len(digits)) > 1:
            return ""

        # Decide which queue to start with
        result = []
        if len(digits) >= len(chars):
            first, second = digits, chars
        else:
            first, second = chars, digits

        # Form the reformatted string
        while first and second:
            result.append(first.popleft())
            result.append(second.popleft())

        if first:
            result.append(first.popleft())
        
        return "".join(result)

The deque class from the collections module in Python is used because it provides efficient operations for removing elements from and adding elements to both ends of a queue. The popleft method removes and returns the element at the front of the queue. The join function is used to join all the elements of the result list into a string.