Construct k palindrome strings

Hash Table String Greedy Counting

68.6% acceptance

Feb 25, 2026

1793

160

Given a string s and an integer k, return true if you can use all the characters in s to construct non-empty k palindrome strings or false otherwise.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn can_construct(s: String, k: i32) -> bool {
    let n = s.len() as i32;
    if k > n { return false; }
    // Count characters with odd frequency
    let mut cnt = [0i32; 26];
    for b in s.bytes() { cnt[(b - b'a') as usize] += 1; }
    let odd_count = cnt.iter().filter(|&&c| c % 2 == 1).count() as i32;
    // Need at least odd_count palindromes (each odd-freq char needs its own center)
    odd_count <= k
  }
}