Swap For Longest Repeated Character Substring Problem

Problem

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.

Examples

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.

Solution

Method 1 – Sliding Window and Character Grouping

Intuition

The key is to find the longest substring of repeated characters, possibly by swapping one character from elsewhere in the string. We can group consecutive same characters and, for each group, check if we can extend it by swapping in another occurrence of the same character from outside the group.

Approach

1. Count the total occurrences of each character in the string.
2. Group consecutive same characters and store their start, end, and length.
3. For each group, consider:
   • The length of the group itself.
   • If there is another group of the same character separated by one different character, try merging them (if total count allows).
   • The answer is the maximum possible length found.
4. Return the maximum length.

Code

C++

class Solution {
public:
    int maxRepOpt1(string text) {
        vector<int> cnt(26, 0);
        for (char c : text) cnt[c - 'a']++;
        int ans = 0, n = text.size();
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && text[j] == text[i]) j++;
            int len = j - i;
            int k = j + 1;
            while (k < n && text[k] == text[i]) k++;
            int merged = len;
            if (j < n && j + 1 < n && text[j + 1] == text[i]) {
                int l2 = 0, t = j + 1;
                while (t < n && text[t] == text[i]) { l2++; t++; }
                merged += l2;
            }
            ans = max(ans, min(cnt[text[i] - 'a'], merged + (merged > len ? 0 : 1)));
            ans = max(ans, min(cnt[text[i] - 'a'], len + (cnt[text[i] - 'a'] > len ? 1 : 0)));
            i = j;
        }
        return ans;
    }
};

Go

func maxRepOpt1(text string) int {
    cnt := make(map[byte]int)
    for i := 0; i < len(text); i++ {
        cnt[text[i]]++
    }
    ans := 0
    n := len(text)
    i := 0
    for i < n {
        j := i
        for j < n && text[j] == text[i] {
            j++
        }
        len1 := j - i
        merged := len1
        if j < n-1 && text[j+1] == text[i] {
            k := j + 1
            for k < n && text[k] == text[i] {
                k++
            }
            merged += k - (j + 1)
        }
        if merged < cnt[text[i]] {
            ans = max(ans, merged+1)
        } else {
            ans = max(ans, merged)
        }
        if len1 < cnt[text[i]] {
            ans = max(ans, len1+1)
        } else {
            ans = max(ans, len1)
        }
        i = j
    }
    return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }

Java

class Solution {
    public int maxRepOpt1(String text) {
        int[] cnt = new int[26];
        for (char c : text.toCharArray()) cnt[c - 'a']++;
        int ans = 0, n = text.length();
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && text.charAt(j) == text.charAt(i)) j++;
            int len = j - i;
            int merged = len;
            if (j < n - 1 && text.charAt(j + 1) == text.charAt(i)) {
                int k = j + 1;
                while (k < n && text.charAt(k) == text.charAt(i)) k++;
                merged += k - (j + 1);
            }
            ans = Math.max(ans, Math.min(cnt[text.charAt(i) - 'a'], merged < cnt[text.charAt(i) - 'a'] ? merged + 1 : merged));
            ans = Math.max(ans, Math.min(cnt[text.charAt(i) - 'a'], len < cnt[text.charAt(i) - 'a'] ? len + 1 : len));
            i = j;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maxRepOpt1(text: String): Int {
        val cnt = IntArray(26)
        for (c in text) cnt[c - 'a']++
        var ans = 0
        var i = 0
        val n = text.length
        while (i < n) {
            var j = i
            while (j < n && text[j] == text[i]) j++
            val len = j - i
            var merged = len
            if (j < n - 1 && text[j + 1] == text[i]) {
                var k = j + 1
                while (k < n && text[k] == text[i]) k++
                merged += k - (j + 1)
            }
            ans = maxOf(ans, minOf(cnt[text[i] - 'a'], if (merged < cnt[text[i] - 'a']) merged + 1 else merged))
            ans = maxOf(ans, minOf(cnt[text[i] - 'a'], if (len < cnt[text[i] - 'a']) len + 1 else len))
            i = j
        }
        return ans
    }
}

Python

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        from collections import Counter
        cnt = Counter(text)
        ans = 0
        n = len(text)
        i = 0
        while i < n:
            j = i
            while j < n and text[j] == text[i]:
                j += 1
            length = j - i
            merged = length
            if j < n - 1 and text[j + 1] == text[i]:
                k = j + 1
                while k < n and text[k] == text[i]:
                    k += 1
                merged += k - (j + 1)
            ans = max(ans, min(cnt[text[i]], merged + (1 if merged < cnt[text[i]] else 0)))
            ans = max(ans, min(cnt[text[i]], length + (1 if length < cnt[text[i]] else 0)))
            i = j
        return ans

Rust

use std::collections::HashMap;
impl Solution {
    pub fn max_rep_opt1(text: String) -> i32 {
        let cnt = text.chars().fold(HashMap::new(), |mut m, c| { *m.entry(c).or_insert(0) += 1; m });
        let s: Vec<char> = text.chars().collect();
        let n = s.len();
        let mut ans = 0;
        let mut i = 0;
        while i < n {
            let mut j = i;
            while j < n && s[j] == s[i] { j += 1; }
            let len = j - i;
            let mut merged = len;
            if j < n - 1 && s[j + 1] == s[i] {
                let mut k = j + 1;
                while k < n && s[k] == s[i] { k += 1; }
                merged += k - (j + 1);
            }
            let total = *cnt.get(&s[i]).unwrap();
            ans = ans.max(std::cmp::min(total, merged + if merged < total { 1 } else { 0 }));
            ans = ans.max(std::cmp::min(total, len + if len < total { 1 } else { 0 }));
            i = j;
        }
        ans as i32
    }
}

TypeScript

class Solution {
    maxRepOpt1(text: string): number {
        const cnt: Record<string, number> = {};
        for (const c of text) cnt[c] = (cnt[c] || 0) + 1;
        let ans = 0, n = text.length, i = 0;
        while (i < n) {
            let j = i;
            while (j < n && text[j] === text[i]) j++;
            const len = j - i;
            let merged = len;
            if (j < n - 1 && text[j + 1] === text[i]) {
                let k = j + 1;
                while (k < n && text[k] === text[i]) k++;
                merged += k - (j + 1);
            }
            const total = cnt[text[i]];
            ans = Math.max(ans, Math.min(total, merged < total ? merged + 1 : merged));
            ans = Math.max(ans, Math.min(total, len < total ? len + 1 : len));
            i = j;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of the string, as each character is visited a constant number of times.
• 🧺 Space complexity: O(1), since the alphabet size is constant.