Skip to content

1370. Increasing Decreasing String 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  string sortString(string s) {
    string ans;
    vector<int> count(26);

    for (const char c : s)
      ++count[c - 'a'];

    while (ans.length() < s.size()) {
      for (int i = 0; i < 26; ++i) {
        if (count[i] == 0)
          continue;
        ans += 'a' + i;
        --count[i];
      }
      for (int i = 25; i >= 0; --i) {
        if (count[i] == 0)
          continue;
        ans += 'a' + i;
        --count[i];
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public String sortString(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    while (sb.length() < s.length()) {
      for (int i = 0; i < 26; i++) {
        if (count[i] == 0)
          continue;
        sb.append((char) (i + 'a'));
        --count[i];
      }
      for (int i = 25; i >= 0; i--) {
        if (count[i] == 0)
          continue;
        sb.append((char) (i + 'a'));
        --count[i];
      }
    }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def sortString(self, s: str) -> str:
    ans = []
    count = collections.Counter(s)

    while count:
      for chars in string.ascii_lowercase, reversed(string.ascii_lowercase):
        ans += [c for c in chars if c in count]
        count -= dict.fromkeys(count, 1)

    return ''.join(ans)