You are given a string text. You can swap two of the characters in the text.

Return the length of the longest substring with repeated characters.

&nbsp;
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" with length 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" with length 6.


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= text.length &lt;= 2 * 104
	text consist of lowercase English characters only.


class Solution:
    def maxRepOpt1(self, text: str) -> int:
        char_groups = []
        
        for char, group in groupby(text):
            group_len = len(list(group))
            char_groups.append((char, group_len))
        
        char_count = Counter(text)
        
        longest_substr_len = 1 # Each char itself is substring of len 1
        
        # Scenario-1: Get the longest substr length by just adding one more char to each group
        for char, group_len in char_groups:
            # NOTE: If the total count of the char across full string is < group_len+1,
            # make sure to take the total count only
            #
            # It means we don't have any extra char occurrence which we can add to the current group
            
            group_len_w_one_addition = min(group_len+1, char_count[char])
            longest_substr_len = max(longest_substr_len, group_len_w_one_addition)
        
        
        # Scenario-2: 
        # If there are two groups of same char, separated by a group of different char with length=1:
        #   1) We can either swap that one char in the middle with the same char as those two groups 
        #       Ex: 'aaa b aaa c a'
        #           - We can swap the 'b' in between two groups of 'a' using same char 'a' from last index
        #           - So after swapping, it will become 'aaa a aaa c b' 
        #           - hence longest substr len of same char 'a' = 7
        #
        #   2) We can merge the two groups
        #       Ex: 'aaa b aaa' 
        #           -> here there are two groups of char 'a' with len = 3 each.
        #           -> they are separated by a group of char 'b' with len = 1
        #           -> hence, we can merge both groups of char 'a' - so that longest substr len = 6
        #           -> basically, swap the 'b' with 'a' at very last index
        #           -> the final string will look like 'aaaaaa b'
        #
        #   We will take max length we can get from above two options.
        #
        # Since we need to check the group prior to curr_idx "i" and also next to curr_idx "i";
        # we will iterate from i = 1 to i = len(char_groups)-2 -- both inclusive
        
        for i in range(1, len(char_groups)-1):
            prev_group_char, prev_group_len = char_groups[i-1]
            curr_group_char, curr_group_len = char_groups[i]
            next_group_char, next_group_len = char_groups[i+1]
            
            if curr_group_len != 1 or prev_group_char != next_group_char:
                continue
                
            len_after_swapping = min(prev_group_len + next_group_len + 1, char_count[next_group_char])
            longest_substr_len = max(longest_substr_len, len_after_swapping)
        
        return longest_substr_len
class Solution {
		public int maxRepOpt1(String s) {
		   int[] count = new int[26];
		   int[] left = new int[s.length()];
		   int[] right = new int[s.length()];
			int max =0;
			// Left Array Containing Length Of Subarray Having Equal Characters Till That Index
			for(int i=0;i<s.length();i++){
				count[s.charAt(i) -'a']++;
				if(i> 0){
					if(s.charAt(i) == s.charAt(i-1)){
						left[i] = left[i-1]+1;
					}else{
						left[i] = 1;
					}
				}else{
					left[i] =1;
				}
				max = Math.max(max,left[i]);
			}
			// Right Array Containing Length Of Subarray Having Equal Characters Till That Index
			for(int i=s.length()-1;i>=0;i--){
				if(i < s.length()-1){
					if(s.charAt(i+1) == s.charAt(i)){
						right[i] = right[i+1] +1;
					}else{
						right[i] =1;
					}
				}else{
					right[i] = 1;
				}
			}
			// Count The Length Of SubString Having Maximum Length When A Character Is Swapped
			for(int i=1 ; i<s.length()-1 ; i++){
				if(s.charAt(i-1) == s.charAt(i+1) && s.charAt(i) != s.charAt(i-1)){
					if(count[s.charAt(i-1) -'a'] == left[i-1] + right[i+1]){
						max = Math.max(max , left[i-1] + right[i+1]);
					}else{
						max = Math.max(max,left[i-1] + right[i+1]+1);
					}
				}else{
					if(count[s.charAt(i) -'a'] == left[i]){
						max = Math.max(max,left[i]);
					}
					else{
						max = Math.max(max,left[i]+1);
					}
				}
			}
			 if(count[s.charAt(s.length()-1)-'a']!=left[s.length()-1])
					{
						max = Math.max(max, left[s.length()-1]+1);
					}
		   return max; 
		}
	}
	
class Solution {
public:
    int maxRepOpt1(string text) {
        vector<pair<int, int>> intervals[26];
        // a: [st, ed], .....
        for(int i = 0; i < text.size();){
            int st = i, ed = i;
            while(i < text.size() && text[i] == text[st]){
                ed = i;
                i++;
            }
            intervals[text[st] - 'a'].push_back({st, ed});
        }
        
        int ans = 0;
        for(int i = 0; i < 26; i++){
            for(int j = 0; j < intervals[i].size(); j++){
                // 单个的最大值
                int len1 = intervals[i][j].second - intervals[i][j].first + 1;
                if(intervals[i].size() > 1)
                    len1++;
                ans = max(ans, len1);
                
                // 合并
                // [1, 2] [4, 6]
                if(j+1 < intervals[i].size() && intervals[i][j].second + 2 == intervals[i][j+1].first){
                    int len2 = intervals[i][j].second - intervals[i][j].first + 1 + intervals[i][j+1].second - intervals[i][j+1].first + 1;
                    if(intervals[i].size() > 2){ // 一定有一个愿意牺牲
                        len2++;
                    }
                    ans = max(ans, len2);
                }
            }
        }
        
        return ans;
    }
};

/**
abababababac

*/
/**
 * @param {string} text
 * @return {number}
 */

const getLast = (ar)=> ar[ar.length-1];
 var maxRepOpt1 = function(text) {

    let freq = {};

    // compute frequency map
    for(let i=0;i<text.length;i++){
        let e=text[i];
        !freq[e] && (freq[e]=0);
        freq[e]++;
    }

    let segments = [];
    segments.push({
        v:text[0],
        c:1
    });

    let max = 1;
    for(let i=1;i<text.length;i++){
        let e = text[i];
        let last = getLast(segments);

        if(last.v == e){
            last.c++;
            max = Math.max(max,last.c);
        }else{
            segments.push({v:e,c:1});
        }
    }

    for(let i=0,len=segments.length;i<len;i++){
        let {v,c} = segments[i];
        if(freq[v] > c){ // x x a , a x x , x a x
            max = Math.max(max,c+1);
        }
        if(i+2<len && v==segments[i+2].v){ // x a x a x a x a x x a x a
            let sum = c+segments[i+2].c;
            if(segments[i+1].c == 1){
                if(freq[v] > sum){
                    max = Math.max(max,1+sum);
                }else{
                    max = Math.max(max,sum);
                }
            }
        }
    }

    return max;

};
Swap For Longest Repeated Character Substring