【天天速看料】Leetcode 1156. 单字符重复子串的最大长度

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

【天天速看料】Leetcode 1156. 单字符重复子串的最大长度

2023-06-04 16:04:09 来源：博客园

【资料图】

题目：

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。给你一个字符串text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

难度：中等

示例1：

输入：text = "ababa"输出：3

示例2：

输入：text = "aaabaaa"输出：6

示例3：

输入：text = "aaabbaaa"输出：4

示例4：

输入：text = "aaaaa"输出：5

示例5：

输入：text = "abcdef"输出：1

提示：

1 <= text.length <= 20000
text仅由小写英文字母组成。

代码实现：

class Solution {public:    int maxRepOpt1(string text) {        int n = text.size();        unordered_map hash; // 统计字符数量        for(auto c : text) ++hash[c];        int maxlen = 0; // 存结果        int cnt[n], idx = -1;    // 将 aaabbaa 处理为 (a, 3) (b, 2) (a, 2)的形式        for(int i = 0; i < n; ++i){            // 统计连续字符            int j = i;            while(j < n && text[j] == text[i]) ++j;     // 统计到连续字符的下一个            cnt[++idx] = j - i;    // 统计以text[i]开始的连续字符长度;            // 判断存在两个相同子串 且 中间间隔一个不同字符            if(idx > 1 && cnt[idx - 1] == 1 && i > 1 && text[i - 2] == text[i]){                maxlen = max(maxlen, min(cnt[idx] + cnt[idx - 2] + 1, hash[text[i]]));            }            maxlen = max(maxlen, min(cnt[idx] + 1, hash[text[i]]));     // 其他情况时，小于总数则+1;            i = j - 1;  // 直接扫描下一个不同字符        }        return maxlen;    }};

关键词：