LeetCode Entry

1400. Construct K Palindrome Strings

11.01.2025 medium 2025 kotlin rust

Can make k palindromes from string?

1400. Construct K Palindrome Strings medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/861

Problem TLDR

Can make k palindromes from string? #medium

Intuition

The main difficulty is to define how chars frequencies can be used to make k palindromes:

  • chars number must be at least k, this is a lower boundary
  • the odd frequencies count must be <= k, this is a higher boundary
  • even frequencies are all dissolved into any number of palindromes

Approach

  • to find those rules on the fly, we should do attempts on examples (by running the code, or writing them down, or imagine if you can)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\), O(n) for Kotlin golf

Code


    fun canConstruct(s: String, k: Int) =
        k <= s.length && s.groupBy { it }
            .values.sumBy { it.size % 2 } <= k



    pub fn can_construct(s: String, k: i32) -> bool {
        let (mut f, k) = (vec![0; 26], k as usize);
        for b in s.bytes() { f[(b - b'a') as usize] += 1 }
        k <= s.len() &&
          (0..26).map(|b| f[b] % 2).sum::<usize>() <= k
    }



    bool canConstruct(string s, int k) {
        int f[26] = {0}, c = 0;
        for (int i = 0; i < s.size(); ++i) c += 2 * (++f[s[i] - 'a'] % 2) - 1;
        return k <= s.size() && c <= k;
    }