知识星球 英雄算法联盟 五月集训 贪心第四题

 

---

目录

 一、题目

1、题目描述

2、基础框架

3、原题链接

二、解题报告

1、思路分析

2、代码详解

三、本题小知识

---

 一、题目
1、题目描述

给你一个字符串 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 中每个字符单独构成一个字符串。

示例 4：

输入：s = "yzyzyzyzyzyzyzy", k = 2
输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。

示例 5：

输入：s = "cr", k = 7
输出：false
解释：我们没有足够的字符去构造 7 个回文串。

2、基础框架

   Java 版本给出的基础框架代码如下：   

class Solution {
    public boolean canConstruct(String s, int k) {
}

提示：

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

3、原题链接

    LeetCode 1400. 构造 K 个回文字符串

二、解题报告
1、思路分析

首先思考一个字符串中的字母能构成多少个回文串

• 显然最多的个数为字符串中元素的个数，即一个元素为一个回文串
• asa、absssba、aabbssscccsssbbaa……
• 一个回文串中最多有一个字母出现奇数次且该字母要放中间，
• 因此一个字符串中若有n个不相同的字母出现奇数次则最少要n个回文串，才能保证每个子串为回文串
• 一个字符串可以构成回文串个数在[min,max]之间，经过上面分析明显，min=Max(n,1)、max=s.length();

能不能构成k个回文串

• 只需要判断k在不在[min,max]之间，若在则true，否则false
• 例如：s="aabbsss" max=7,即每个字母为一个回文串，min=1，absssba
• absssba可分为，s，abssba、abssba又分为 s,absba，absba又可以分为s，abba
• 依此把奇数次的从中间的拿出来可得到两个回文串，故k若在[min,max]之间则返回true

 

 

2、代码详解

class Solution {
    public boolean canConstruct(String s, int k) {
        int max=0;
        int min=0;
        //最多可以构成回文串数位元素个数
        max=s.length();

        int[]count=new int[26];
        //遍历统计每个字母出现的次数
        char[] chars=s.toCharArray();
        for(int i=0;i=min&&k<=max;
    }
}

三、本题小知识

  回文串，最多最少