DDSA Solutions

1400. Construct K Palindrome Strings

UnknownView on LeetCode
Hash TableStringGreedyCounting
Time: O(n)
Space: O(1)

Problem Overview

Check if string can be rearranged into k palindrome groups.

Intuition

Check if string can be rearranged into k palindrome groups. Count character frequencies. Characters with odd frequency need one middle slot each. Need at most k odd-frequency characters.

Algorithm

  1. 1Count character frequencies.
  2. 2Count how many have odd frequency.
  3. 3Return odd_count <= k <= s.length.

Common Pitfalls

  • •Each palindrome string can absorb at most one odd-frequency character as center. Also k must be <= s.length.
1400.cs
C#
// Approach: Count characters with odd frequency; need at least that many palindromes; also need |s| >= k.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool CanConstruct(string s, int k)
    {
        // If |s| < k, we cannot construct k strings from the s.
        if (s.Length < k)
            return false;

        int[] count = new int[26];

        foreach (char c in s)
            count[c - 'a'] ^= 1;

        // If the number of letters that have odd counts > k, the minimum number of
        // palindromic strings we can construct is > k.
        return count.Count(c => c % 2 == 1) <= k;
    }
}
Was this solution helpful?

Related Problems