算法每日一题：构造限制重复的字符串 | 字符串 | 数组与哈希联系

大家好，我是星恒
今天的每日一题虽然是一道中等题，但是思路并不难，中规中矩的按照题意写下来就差不多了过了
只不过其中的一些处理细节值得我们去学习

题目：leetcode 2182
给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构造一个新字符串 repeatLimitedString ，使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的_ _repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同，那么较长的字符串字典序更大。
示例：
示例 1：

输入：s = "cczazcc", repeatLimit = 3
输出："zzcccac"
解释：使用 s 中的所有字符来构造 repeatLimitedString "zzcccac"。
字母 'a' 连续出现至多 1 次。
字母 'c' 连续出现至多 3 次。
字母 'z' 连续出现至多 2 次。
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。
该字符串是字典序最大的 repeatLimitedString ，所以返回 "zzcccac" 。
注意，尽管 "zzcccca" 字典序更大，但字母 'c' 连续出现超过 3 次，所以它不是一个有效的 repeatLimitedString 。

示例 2：

输入：s = "aababab", repeatLimit = 2
输出："bbabaa"
解释：
使用 s 中的一些字符来构造 repeatLimitedString "bbabaa"。 
字母 'a' 连续出现至多 2 次。 
字母 'b' 连续出现至多 2 次。 
因此，没有字母连续出现超过 repeatLimit 次，字符串是一个有效的 repeatLimitedString 。 
该字符串是字典序最大的 repeatLimitedString ，所以返回 "bbabaa" 。 
注意，尽管 "bbabaaa" 字典序更大，但字母 'a' 连续出现超过 2 次，所以它不是一个有效的 repeatLimitedString 。

提示：

• 1 <= repeatLimit <= s.length <= 105
• s 由小写英文字母组成

分析：
本题中，我们可以把字符串s中的字符存入hash中，键为26个字母，值为出现的次数，以方便我们随取随用；
资源准备好了，我们开始拼接字典序最大的字符串吧：
首先遍历字母数组，然后一个一个字母拼到字母中
我们肯定时希望前面的字母越大越好，但是由于有连续出现次数的限制，所以我们在到达限制时，我们找到第二大的字母插入一个，然后继续插入当前最大的字母；
当我们将当前大字母填完之后，就开始下一个字母的填写
题解：

class Solution {
    static public int N = 26;
    public String repeatLimitedString(String s, int repeatLimit) {
        int[] count = new int[N];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        StringBuilder ret = new StringBuilder();
        int m = 0;
        for (int i = N - 1, j = N - 2; i >= 0 && j >= 0;) {
            if (count[i] == 0) { // 当前字符已经填完，填入后面的字符，重置 m
                m = 0;
                i--;
            } else if (m < repeatLimit) { // 当前字符未超过限制
                count[i]--;
                ret.append((char)('a' + i));
                m++;
            } else if (j >= i || count[j] == 0) { // 当前字符已经超过限制，查找可填入的其他字符
                j--;
            } else { // 当前字符已经超过限制，填入其他字符，并且重置 m
                count[j]--;
                ret.append((char)('a' + j));
                m = 0;
            }
        }
        return ret.toString();
    }
}

拓展：

1. 字符的存储

刚开始我想的是使用hash来存储，但是看了题解后，很明显，存储26个字母使用数组更优雅

2. StringBuilder和StringBuilder

String 底层值char[]型常量，修改他，java底层会给他重新创建一个空间来存储修改值
而StringBuilder和StringBuffer，底层是char[]型，是变量，修改值，会在原来的空间直接修改

StringBuffer和StringBuilder中常用的方法：

StringBuffer append(xxx)：拼接字符串
StringBuffer delete(int start,int end)：删除指定范围的内容,左开右闭
StringBuffer replace(int start, int end, String str)：替换指定范围的内容
StringBuffer insert(int offset, xxx)：在指定位置插入指定的内容
StringBuffer reverse() ：把当前字符序列逆转

public int indexOf(String str) : 返回指定子字符串在当前字符串中第一次出现处的索引
public String substring(int start,int end) ：返回指定范围的子字符串
public int length() : 返回字符串的长度
public char charAt(int n ) : 获取指定索引处的字符
public void setCharAt(int n ,char ch) : 设置指定索引处的字符

面试题：String、StringBuffer和StringBuilder的异同？
相同点：底层都是通过char数组实现的
不同点：
String对象一旦创建，其值是不能修改的，如果要修改，会重新开辟内存空间来存储修改之后的对象；而StringBuffer和StringBuilder对象的值是可以被修改的；
StringBuffer几乎所有的方法都使用synchronized实现了同步，线程比较安全，在多线程系统中可以保证数据同步，但是效率比较低；而StringBuilder 没有实现同步，线程不安全，在多线程系统中不能使用 StringBuilder，但是效率比较高。
如果我们在实际开发过程中需要对字符串进行频繁的修改，不要使用String，否则会造成内存空间的浪费；当需要考虑线程安全的场景下使用 StringBuffer，如果不需要考虑线程安全，追求效率的场景下可以使用 StringBuilder。
由于我们这道题救过ret要不断被更新，又因为这是算法题追求效率，所以我们这道题使用StringBuilder来做更合适

关于此点，大家可以参考这篇帖子：深入理解String，StringBuffer和StringBuilder



如果大家有什么思考和问题，可以在评论区讨论，也可以私信我，很乐意为大家效劳。
好啦，今天的每日一题到这里就结束了，如果大家觉得有用，可以可以给我一个小小的赞呢，我们下期再见！