1156. 单字符重复子串的最大长度

￡神魔★判官ぃ 2022-11-26 04:58 142阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]  
[leetcode][]

两种情况，交换或者不交换，交换的情况又分两种，交换后只多一个，交换后多了一串，aaabbaaa 这种是交换后只多一个的情况， aaabaaa交换后多一串的情况，abcdf不交换的情况。

遍历两次就行，第一次记录每个字符总数，和不交换情况下最长长度  
第二次考虑交换的情况

class Solution {
        
    public:
        int maxRepOpt1(string text) {
        
            if(text.size() == 0) return 0;
            map<char, int> mp;
            int max = 0;
            int i = 0;
            int j = 0;
            while(i < text.size()){
        
                int count = 0;
                char ch = text[i];
                while(j < text.size() && ch == text[j]){
        
                    count++;
                    j++;
                    mp[ch]++;
                }
                if(count > max) max = count; //计算出不交换时的最大重复子串长度
                i = j;
            }
            
            i = 0; j = 0;
            while(i < text.size()){
         // 再次遍历一次字符串，找出只隔一位且可以交换合并的两个相同重复子串
                int count = 0;
                char ch = text[i];
                while(j < text.size() && ch == text[j]){
        
                    count++;
                    j++;
                }
                if(j+1 < text.size() && text[j+1] == ch) {
         //隔一个不同字符
                    int k = j+1;
                    while(k < text.size() && ch == text[k]){
        
                    count++;
                    k++;
                    if(mp[ch] > count && max < count+1) max = count+1; //字符总数足够可交换
                    } 
                }else if(mp[ch] > count && max < count+1) max = count+1; //隔多个不同字符，交换一位
                i = j;
            }
    
            return max;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20221124/4aeb649792c14e8383afb861aca67e1e.png
[leetcode]: https://leetcode-cn.com/problems/swap-for-longest-repeated-character-substring/