Java O(n)
1, Count all characters\' appearance as a pool (cnt[])\n2, append those characters based on availability in the pool\n\n    public String sortString(String s) {
1, Count all characters\' appearance as a pool (cnt[])\n2, append those characters based on availability in the pool\n```\n    public String sortString(String s) {\n        int n = s.length(), cnt[] = new int[26];\n        for (char c : s.toCharArray()) cnt[c - \'a\']++;\n        StringBuilder sb = new StringBuilder();\n        while (n > 0) {\n            for (int i = 0; i < 26 && n > 0; i++) {\n                if (cnt[i] > 0) {\n                    cnt[i]--;\n                    sb.append((char) (\'a\' + i));\n                    n--;\n                }\n            }\n            for (int i = 25; i >= 0 && n > 0; i--) {\n                if (cnt[i] > 0) {\n                    cnt[i]--;\n                    sb.append((char) (\'a\' + i));\n                    n--;\n                }\n            }\n        }\n        return sb.toString();\n    }\n```
[]