1400. Construct K Palindrome Strings

Description

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.

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.
1 <= k <= 10⁵

Solutions

Solution 1: Counting

First, we check if the length of string \(s\) is less than \(k\). If it is, we cannot construct \(k\) palindrome strings, so we can directly return false.

Otherwise, we use a hash table or an array \(cnt\) to count the occurrences of each character in string \(s\). Finally, we only need to count the number of characters \(x\) that appear an odd number of times in \(cnt\). If \(x\) is greater than \(k\), we cannot construct \(k\) palindrome strings, so we return false; otherwise, we return true.

The time complexity is \(O(n)\), and the space complexity is \(O(C)\). Where \(n\) is the length of string \(s\), and \(C\) is the size of the character set, here \(C=26\).

Python3JavaC++GoTypeScript

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        cnt = Counter(s)
        return sum(v & 1 for v in cnt.values()) <= k

class Solution {
    public boolean canConstruct(String s, int k) {
        int n = s.length();
        if (n < k) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        int x = 0;
        for (int v : cnt) {
            x += v & 1;
        }
        return x <= k;
    }
}

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k) {
            return false;
        }
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
        }
        int x = 0;
        for (int v : cnt) {
            x += v & 1;
        }
        return x <= k;
    }
};

func canConstruct(s string, k int) bool {
    if len(s) < k {
        return false
    }
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    x := 0
    for _, v := range cnt {
        x += v & 1
    }
    return x <= k
}

function canConstruct(s: string, k: number): boolean {
    if (s.length < k) {
        return false;
    }
    const cnt: number[] = new Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    let x = 0;
    for (const v of cnt) {
        x += v & 1;
    }
    return x <= k;
}

1400. Construct K Palindrome Strings

Description

Solutions

Solution 1: Counting

Comments