[Java/Python 3] Two clean codes w/ explanation and analysis.
Q & A:\n\nQ1: TreeSet<>(tm.keySet()) vs TreeSet(tm.descendingKeySet()).\nIn first Java code, I thought TreeSet will always sort from small to large, if you don\
**Q & A:**\n\nQ1: TreeSet<>(tm.keySet()) vs TreeSet(tm.descendingKeySet()).\nIn first Java code, I thought TreeSet will always sort from small to large, if you don\'t specify descending order, no matter what order you put in the ().. can you explain why this works..\n\nA1: `TreeSet(SortedSet())` will use the same ordering  as the `SortedSet()`.\n\n**End of Q & A.**\n\n----\n**Java**\n1. Use TreeMap to count each char in `s`;\n2. Append to StringBuilder the keys in TreeMap in sorted order, decrease the count of each key, and remove the entry if reaching `0`;\n3. Do the similar operation in step 2, but in descending order of the keys;\n4. Repeat 2 and 3 till the TreeMap is empty.\n\n```java\n    public String sortString(String s) {\n        StringBuilder ans = new StringBuilder();\n        TreeMap<Character, Integer> tm = new TreeMap<>();\n        for (char c : s.toCharArray()) {\n            tm.put(c, 1 + tm.getOrDefault(c, 0));\n        }\n        boolean asc = true;\n        while (!tm.isEmpty()) {\n            for (char c : asc ? new TreeSet<>(tm.keySet()) : new TreeSet(tm.descendingKeySet())) {\n                ans.append(c);\n                tm.put(c, tm.get(c) - 1);\n                tm.remove(c, 0);\n            }\n            asc = !asc; // same as asc ^= true;\n        }\n        return ans.toString();\n    }\n```\nUse array instead of TreeMap to get better time performance. runtime: 1 ms, beat 100%.\n```java\n    public String sortString(String s) {\n        StringBuilder ans = new StringBuilder();\n        int[] count = new int[26];\n        for (char c : s.toCharArray())\n            ++count[c - \'a\'];\n        while (ans.length() < s.length()) {\n            add(count, ans, true);\n            add(count, ans, false);\n        }\n        return ans.toString();\n    }\n    private void add(int[] cnt, StringBuilder ans, boolean asc) {\n        for (int i = 0; i < 26; ++i) {\n            int j = asc ? i : 25 - i;\n            if (cnt[j]-- > 0)\n                ans.append((char)(j + \'a\'));\n        }\n    }\n```\n**Python 3**\n```python\n    def sortString(self, s: str) -> str:\n        cnt, ans, asc = collections.Counter(s), [], True\n        while cnt:                                                                  # if Counter not empty.\n            for c in sorted(cnt) if asc else reversed(sorted(cnt)):                 # traverse keys in ascending/descending order.\n                ans.append(c)                                                       # append the key.\n                cnt[c] -= 1                                                         # decrease the count.\n                if cnt[c] == 0:                                                     # if the count reaches to 0.\n                    del cnt[c]                                                      # remove the key from the Counter.\n            asc = not asc                                                           # change the direction, same as asc ^= True.\n        return \'\'.join(ans)\n```\nSimilar version, but no removal of key from the Counter.\n```python\n    def sortString(self, s: str) -> str:\n        cnt, ans, asc  = collections.Counter(s), [], True\n        while len(ans) < len(s):                                # if not finish.\n            for i in range(26):                                 # traverse lower case letters.\n                c = string.ascii_lowercase[i if asc else ~i]    # in ascending/descending order.\n                if cnt[c] > 0:                                  # if the count > 0.\n                    ans.append(c)                               # append the character.\n                    cnt[c] -= 1                                 # decrease the count.\n            asc = not asc                                       # change direction.\n        return \'\'.join(ans)\n```\n**Analysis:**\nSince there are only `26` distinct lower case letters, sorting and each TreeMap operation cost at most `26 * log26`, which can be regarded as a constant.\n\nTime & space: `O(n)`, where `n` = `s.length()`.
[]