Construct the longest new string

Math Dynamic Programming Greedy Brainteaser

54.6% acceptance

Feb 25, 2026

339

You are given three integers x, y, and z. You have x strings equal to "AA", y strings equal to "BB", and z strings equal to "AB". You want to choose some (possibly all or none) of these strings and concatenate them in some order to form a new string. This new string must not contain "AAA" or "BBB" as a substring. Return the maximum possible length of the new string. A substring is a contiguous non-empty sequence of characters within a string.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_string(x: i32, y: i32, z: i32) -> i32 {
    // "AB" can always be used. "AA" and "BB" must alternate.
    // min(x,y) pairs of (AA BB) + 1 extra AA or BB if x != y
    let base = 2 * x.min(y) + if x != y { 1 } else { 0 };
    (base + z) * 2
  }
}