1
class Solution {
2
  public String reformat(String s) {
3

4
    List<Character> ch = new ArrayList<>();
5
    List<Character> d = new ArrayList<>();
6

7
    for (char c : s.toCharArray()) {
8
      if (c >= 'a' && c <= 'z') ch.add(c);
9
      else d.add(c);
10
    }
11

12
    if (Math.abs(d.size() - ch.size()) > 1) return "";
13

14
    StringBuilder str = new StringBuilder();
15

16
    for (int i = 0; i < s.length(); i++) {
17

18
      if (!ch.isEmpty() || !d.isEmpty()) {
19
        if (ch.size() > d.size()) str.append(appender(ch, d));
20
        else str.append(appender(d, ch));
21
      } else {
22
        break;
23
      }
24
    }
25

26
    return new String(str);
27
  }
28

29
  public String appender(List<Character> first, List<Character> second) {
30

31
    StringBuilder str = new StringBuilder();
32

33
    if (!first.isEmpty()) {
34
      str.append(first.get(0));
35
      first.remove(0);
36
    }
37
    if (!second.isEmpty()) {
38
      str.append(second.get(0));
39
      second.remove(0);
40
    }
41

42
    return new String(str);
43
  }
44
}