[LeetCode] 1156. Swap For Longest Repeated Character Substring

[grandyang]

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:

Input: text = "aaabbaaa"
Output: 4

Example 4:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:

Input: text = "abcdef"
Output: 1

Constraints:

• 1 <= text.length <= 20000
• text consist of lowercase English characters only.

这道题给了一个字符串 text，说是可以交换任意位置的两个字符一次，问可以得到的最长的重复字符子串的长度。所谓的重复字符的子串就是所有字符都相同的子串，题目中给的例子很好的说明了题意。本题的难点就在于可以交换任意位置的两个字符一次，就好像是在斗地主的时候，总是在关键的位置缺少一张牌，没法形成连牌，而此时假如 joker 可以代替任意一张牌的话，就可能组成连牌。这里交换字符操作也是为了尽可能的让相同的字符靠在一起，如果不考虑代码实现，给你一个字符串，如何找最长的重复子串，博主会数连续相同的字符，若此时有一个不同字符出现了，只要后面还有相同的字符，就会继续数下去，因为有一次交换的机会，什么时候停止呢，当再次出现不同字符的时候就停止，或者是当前统计个数等于该字符出现的总个数时也停止，因为得到的结果不可能超过某个字符出现的总个数。所以可以先统计每个字符的出现次数，然后开始遍历字符，对于每个遍历到的字符，都开始数之后跟其相等的字符，新建变量j，cnt，和 diff，当j小于n，且当前字符和比较字符相同，或者 diff 等于0，且 cnt 小于比较字符出现的总个数时进行遍历，若当前遍历到的字符和要比较的字符不相等，说明该使用交换操作了，diff 自增1，此时将i更新为 j-1，这是一个优化操作，可以避免一些不必要的计算，下次从这个位置往后统计，也相当于重置了 diff。还有就是这个 cnt 小于字符出现总个数这个条件卡的非常好，即便下一个还是相同字符，也不能再统计了，因为最后的这个相同字符可能是要用来交换前面的断点位置的。每次用统计出来的 cnt 更新结果 res，但是一个方向的遍历可能无法应对所有情况，比如 "acbaaa"，若只是从前往后遍历，那么最终只能得到3，而正确的答案是4，因为可以将b和第一个a交换，所以还需要从后往前进行一次相同的操作，这样才能得到正确的答案，参见代码如下：

解法一：

class Solution {
public:
    int maxRepOpt1(string text) {
        int res = 0, n = text.size();
        unordered_map<char, int> charCnt;
        for (char c : text) ++charCnt[c];
        for (int i = 0; i < n; ++i) {
            char cur = text[i];
            int j = i, cnt = 0, diff = 0;
            while (j < n && (text[j] == cur || diff == 0) && cnt < charCnt[cur]) {
                if (cur != text[j]) {
                    ++diff;
                    i = j - 1;
                }
                ++cnt;
                ++j;
            }
            res = max(res, cnt);
        }
        for (int i = n - 1; i >= 0; --i) {
            char cur = text[i];
            int j = i, cnt = 0, diff = 0;
            while (j >= 0 && (text[j] == cur || diff == 0) && cnt < charCnt[cur]) {
                if (cur != text[j]) {
                    ++diff;
                    i = j + 1;
                }
                ++cnt;
                --j;
            }
            res = max(res, cnt);
        }
        return res;
    }
};

上面的解法严格来说还是平方级的，再来看一种线性时间的解法，可能比较难想，由于这里需要关注的是相同字符的出现位置，所以可以将所有相同的字符的位置都放到一个数组中，那么这里就建立一个字符和其出现位置数组之间的映射。由于题目中限制了只有英文字母，所以可以按照每个字母进行遍历，直接遍历每个字符的位置数组，这里新建变量 cnt，cnt2，和 mx，其中 cnt 统计的是连续字母的个数，cnt2 相当于一个临时变量，当使用交换操作时，保存之前的 cnt 值，mx 为二者之和。在遍历完某个字母位置数组之后，最后看一下若该字母出现总个数大于 mx，则说明交换后的字母还没有统计进去，不管之前有没有使用交换操作，都需要加上这个额外的一个，参见代码如下：

解法二：

class Solution {
public:
    int maxRepOpt1(string text) {
        int res = 0, n = text.size();
        unordered_map<char, vector<int>> idxMap;
        for (int i = 0; i < n; ++i) idxMap[text[i]].push_back(i);
        for (char c = 'a'; c <= 'z'; ++c) {
            int cnt = 1, cnt2 = 0, mx = 0;
            for (int i = 1; i < idxMap[c].size(); ++i) {
                if (idxMap[c][i] == idxMap[c][i - 1] + 1) {
                    ++cnt;
                } else {
                    cnt2 = (idxMap[c][i] == idxMap[c][i - 1] + 2) ? cnt : 0;
                    cnt = 1;
                }
                mx = max(mx, cnt + cnt2);
            }
            res = max(res, mx + (idxMap[c].size() > mx ? 1 : 0));
        }
        return res;
    }
};

Github 同步地址:

#1156

参考资料：

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355922/C%2B%2B-2-approaches

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355866/Intuitive-Java-Solution-With-Explanation

LeetCode All in One 题目讲解汇总(持续更新中...)