Increasing Decreasing String Problem & Solution
See the increasing decreasing string problem on LeetCode.
C++ Solution
The runtime complexity of this algorithm is $O(n)$.
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
class Solution {
public:
string sortString(string s) {
string t;
int freq['z' - 'a' + 1] = {};
for (char c : s) {
++freq[c - 'a'];
}
while (t.size() < s.size()) {
for (char c = 'a'; c <= 'z'; ++c) {
if (freq[c - 'a']-- > 0) {
t += c;
}
}
for (char c = 'z'; c >= 'a'; --c) {
if (freq[c - 'a']-- > 0) {
t += c;
}
}
}
return t;
}
};