【力扣每日一题】力扣2182构造限制重复的字符串

题目来源

力扣2182构造限制重复的字符串

题目描述

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

解题思路

1. 先将所给字符串s转为字符数组并；排序
2. 设定两个指针下标，max指向当前最大字符，next指向当前次大字符；
3. 如果最大字符连续出现数未被限制继续放入最大字符，反之放入一个次大字符。

代码实现

java实现

public class Solution {
    public String repeatLimitedString(String s, int repeatLimit) {
        int length = s.length();
        // 给定字符串转为数组并排序
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        // 先将最大字符插入
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(charArray[length - 1]);
        // 访问数组
        boolean[] visit = new boolean[length];
        visit[length - 1] = true;
        // 最大字符指针
        int max = length - 2;
        // 次大字符指针
        int next = max;
        while (next >= 0 && (charArray[next] == charArray[max] || visit[next])) {
            next--;
        }
        // 最大字符连续出现次数
        int continuousCount = 1;
        while (stringBuilder.length() < length) {
            // 如果最大字符是末尾字符串
            if (charArray[max] == stringBuilder.charAt(stringBuilder.length() - 1)) {
                // 当出现次数达到限制次数，插入次大字符
                if (continuousCount == repeatLimit) {
                    // 没有次大字符，则返回结果
                    if (next < 0) {
                        return stringBuilder.toString();
                    }
                    stringBuilder.append(charArray[next]);
                    visit[next--] = true;
                    continuousCount = 0;
                    continue;
                }
                // 未达到最大限制次数，插入最大字符，
                stringBuilder.append(charArray[max]);
                visit[max] = true;
                while (max >= 0 && visit[max]) {
                    max--;
                }
                if (max < 0) {
                    return stringBuilder.toString();
                }
                continuousCount++;
            }else {
                // 如果当前插入字符与上一个插入字符不相等，重置次数、修改次大字符指针
                continuousCount = 1;
                stringBuilder.append(charArray[max]);
                visit[max] = true;
                while (max >= 0 && visit[max]) {
                    max--;
                }
                if (max < 0) {
                    return stringBuilder.toString();
                }
                while (next >= 0 && (charArray[next] == charArray[max] || visit[next])) {
                    next--;
                }
            }
        }
        return stringBuilder.toString();
}

c++实现

class Solution {
public:
    string repeatLimitedString(string s, int repeatLimit) {
        int length = s.length();
        // 字符串转数组并排序
        char* charArray = new char[length];
        for (int i = 0; i < length; i++) {
            charArray[i] = s[i];
        }
        sort(charArray, charArray + length, greater<char>());

        // 访问数组
        bool* visit = new bool[length] {false};
        visit[0] = true;

        string result;
        result += charArray[0];

        bool nextFlag = false;
        // 最大字符下标
        int max = 1;
        // 次大字符下标
        int next = max;
        while (next < length && (charArray[max] == charArray[next] || visit[next])) {
            next++;
        }
        int continuousCount = 1;

        while (result.length() < s.length()) {
            if (charArray[max] == result[result.length() - 1]) {
                if (continuousCount == repeatLimit) {
                    if (next == length) {
                        return result;
                    }
                    // 达到限制插入次大字符
                    result += charArray[next];
                    visit[next--] = true;
                    continuousCount = 0;
                }else {
                    // 未达到限制直接插入
                    result += charArray[max];
                    visit[max] = true;
                    continuousCount++;
                    while (max < length && visit[max]) {
                        max++;
                    }
                    if (max == length) {
                        return result;
                    }
                }
            } else {
                // 如果不同直接加入，修改次大字符
                result += charArray[max];
                visit[max] = true;
                continuousCount = 1;
                while (max < length && visit[max]) {
                    max++;
                }
                if (max == length) {
                    return result;
                }
                while (next < length && (charArray[max] == charArray[next] || visit[next])) {
                    next++;
                }
            }
        }
        return result;
    }
};

算法题记录