Construct string with repeat limit

Hash Table String Greedy Heap (Priority Queue) Counting

70.9% acceptance

Feb 25, 2026

1267

101

You are given a string s and an integer repeatLimit. Construct the lexicographically largest string using characters of s such that no letter appears more than repeatLimit times in a row. Return the lexicographically largest repeatLimitedString possible.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn repeat_limited_string(s: String, repeat_limit: i32) -> String {
    let mut freq = [0i32; 26];
    for b in s.bytes() {
      freq[(b - b'a') as usize] += 1;
    }
    let mut result = String::new();
    let mut i = 25i32; // current largest letter (0-indexed)
    loop {
      // Find next non-empty frequency from i downward
      while i >= 0 && freq[i as usize] == 0 {
        i -= 1;
      }
      if i < 0 {
        break;
      }
      let take = freq[i as usize].min(repeat_limit);
      for _ in 0..take {
        result.push((b'a' + i as u8) as char);
      }
      freq[i as usize] -= take;
      if freq[i as usize] > 0 {
        // Need a different character in between
        let mut j = i - 1;
        while j >= 0 && freq[j as usize] == 0 {
          j -= 1;
        }
        if j < 0 {
          break;
        }
        result.push((b'a' + j as u8) as char);
        freq[j as usize] -= 1;
        // Don't decrement i; continue with i
      } else {
        i -= 1;
      }
    }
    result
  }
}