05 August 2008
给一个字符串 s 和一个整数 k 。用 s 字符串中 所有字符 构造 k 个非空 回文串 。可以构造出k个就返回true，否则返回false
求出字符串 s 最少可以构造的回文串个数 left；
求出字符串 s 最多可以构造的回文串个数 right；
找出在 [left,right] 范围内满足要求的那些值，并判断 k 是否在其中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean canConstruct(String s, int k) {
// 右边界为字符串的长度
int right = s.length();
// 统计每个字符出现的次数
int[] occ = new int[26];
for (int i = 0; i < right; ++i) {
++occ[s.charAt(i) - 'a'];
}
// 左边界为出现奇数次字符的个数
int left = 0;
for (int i = 0; i < 26; ++i) {
if (occ[i] % 2 == 1) {
++left;
}
}
// 注意没有出现奇数次的字符的特殊情况
left = Math.max(left, 1);
return left <= k && k <= right;
}
}