Increasing decreasing string

Hash Table String Counting

77.2% acceptance

Feb 25, 2026

840

878

You are given a string s. Reorder the string using the following algorithm: Remove the smallest character from s and append it to the result. Remove the smallest character from s that is greater than the last appended character, and append it to the result. Repeat step 2 until no more characters can be removed. Remove the largest character from s and append it to the result. Remove the largest character from s that is smaller than the last appended character, and append it to the result. Repeat step 5 until no more characters can be removed. Repeat steps 1 through 6 until all characters from s have been removed. If the smallest or largest character appears more than once, you may choose any occurrence to append to the result. Return the resulting string after reordering s using this algorithm.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sort_string(s: String) -> String {
    let mut count = [0u32; 26];
    for b in s.bytes() { count[(b - b'a') as usize] += 1; }
    let mut result = String::with_capacity(s.len());
    while result.len() < s.len() {
      // ascending
      for i in 0..26 {
        if count[i] > 0 {
          result.push((b'a' + i as u8) as char);
          count[i] -= 1;
        }
      }
      // descending
      for i in (0..26).rev() {
        if count[i] > 0 {
          result.push((b'a' + i as u8) as char);
          count[i] -= 1;
        }
      }
    }
    result
  }
}