C++ Solution using Counting
\nclass Solution {\npublic:\n    string sortString(string s) {\n        string res = "";\n        char prev;\n        vector<int>count(26,0);\n        for(auto 
```\nclass Solution {\npublic:\n    string sortString(string s) {\n        string res = "";\n        char prev;\n        vector<int>count(26,0);\n        for(auto x: s) {\n            count[x-\'a\']++;\n        }\n        \n        int len = s.length();\n        int stage = 0;\n        while(len) {\n            if(stage == 0) {\n                // finding the least\n                for(int j=0 ; j<26 ; j++) {\n                    if(count[j] > 0) {\n                        res += j+\'a\';\n                        prev = j;\n                        stage = 1;\n                        count[j]--;\n                        len--;\n                        break;\n                    }\n                }\n            } else if(stage == 1) {\n                // find the next smallest letter\n                int f = 0;\n                for(int j=prev+1 ; j<26 ; j++) {\n                    if(count[j] > 0) {\n                        count[j]--;\n                        res += j+\'a\';\n                        f = 1;\n                        prev = j;\n                        len--;\n                        break;\n                    }\n                }\n                if(f == 0) {\n                    stage = 2;\n                }\n            } else if(stage == 2) {\n                // find the largest\n                for(int j=25 ; j>=0 ; j--) {\n                    if(count[j] > 0) {\n                        count[j]--;\n                        res+=j+\'a\';\n                        prev = j;\n                        len--;\n                        stage = 3;\n                        break;\n                    }\n                }\n            } else if(stage == 3) {\n                int f = 0;\n                for(int j=prev-1 ; j>=0 ; j--) {\n                    if(count[j]>0) {\n                        count[j]--;\n                        res += j+\'a\';\n                        f = 1;\n                        len--;\n                        prev = j;\n                        break;\n                    }\n                }\n                if(f == 0){\n                    stage = 0;\n                }\n            }\n        }\n        \n        return res;\n    }\n};\n```
['String', 'C', 'Counting']