1400. 构造 K 个回文字符串

题目描述

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空回文串。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

示例 1：

输入：s = "annabelle", k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

示例 2：

输入：s = "leetcode", k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。

示例 3：

输入：s = "true", k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

提示：

1 <= s.length <= 10⁵
s 中所有字符都是小写英文字母。
1 <= k <= 10⁵

解法

方法一：计数

我们先判断字符串 \(s\) 的长度是否小于 \(k\)，如果是，那么一定无法构造出 \(k\) 个回文串，可以直接返回 false。

否则，我们用一个哈希表或数组 \(cnt\) 统计字符串 \(s\) 中每个字符出现的次数。最后，我们只需要统计 \(cnt\) 中奇数次数的字符个数 \(x\)，如果 \(x\) 大于 \(k\)，那么一定无法构造出 \(k\) 个回文串，返回 false；否则，返回 true。

时间复杂度 \(O(n)\)，空间复杂度 \(O(C)\)。其中 \(n\) 是字符串 \(s\) 的长度；而 \(C\) 是字符集大小，这里 \(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. 构造 K 个回文字符串

题目描述

解法

方法一：计数

评论