// Runtime: 2 ms, faster than 99.67% of Java online submissions for Reorder Data in Log Files.
// Memory Usage: 38.9 MB, less than 70.59% of Java online submissions for Reorder Data in Log Files.
class Solution {
    public String[] reorderLogFiles(String[] logs) {
        int len = logs.length;
        String[] ids = new String[len];
        String[] letterPart = new String[len];

        for (int i = 0; i < len; i++) {
            String log = logs[i];

            int spaceIndex = log.indexOf(' ');
            ids[i] = log.substring(0, spaceIndex);

            int idx = spaceIndex;
            while (log.charAt(idx) == ' ') idx++;

            String rest = log.substring(idx);
            if (!Character.isDigit(rest.charAt(0))) {
                letterPart[i] = rest;
            }
        }

        Integer[] indexes = new Integer[len];
        for (int i = 0; i < len; i++) indexes[i] = i;

        Arrays.sort(indexes, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                if (letterPart[a] != null && letterPart[b] != null) {
                    int restCompare = letterPart[a].compareTo(letterPart[b]);

                    if (restCompare != 0) return restCompare;
                    else return ids[a].compareTo(ids[b]);
                }
                else if (letterPart[a] != null && letterPart[b] == null) {
                    return -1;
                }
                else if (letterPart[a] == null && letterPart[b] != null) {
                    return +1;
                }
                else /*(letterPart[a] == null && letterPart[b] == null)*/ {
                    return a - b;
                }
            }
        });

        String[] result = new String[len];
        for (int i = 0; i < len; i++) result[i] = logs[indexes[i]];
        return result;
    }
}