Longest happy string

String Greedy Heap (Priority Queue)

65.5% acceptance

Feb 25, 2026

2797

319

A string s is called happy if it satisfies the following conditions: s only contains the letters 'a', 'b', and 'c'. s does not contain any of "aaa", "bbb", or "ccc" as a substring. s contains at most a occurrences of the letter 'a'. s contains at most b occurrences of the letter 'b'. s contains at most c occurrences of the letter 'c'. Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "". A substring is a contiguous sequence of characters within a string.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_diverse_string(a: i32, b: i32, c: i32) -> String {
    let mut counts = [(a, 'a'), (b, 'b'), (c, 'c')];
    let mut result = String::new();
    loop {
      counts.sort_unstable_by(|x, y| y.0.cmp(&x.0));
      let last2 = if result.len() >= 2 {
        let b = result.as_bytes();
        let n = b.len();
        Some((b[n-2] as char, b[n-1] as char))
      } else { None };
      let idx = if let Some((c1, c2)) = last2 {
        if c1 == c2 && c2 == counts[0].1 {
          if counts[1].0 == 0 { break; }
          1
        } else {
          if counts[0].0 == 0 { break; }
          0
        }
      } else {
        if counts[0].0 == 0 { break; }
        0
      };
      result.push(counts[idx].1);
      counts[idx].0 -= 1;
    }
    result
  }
}