Problem Explanation

The problem is to find the longest substring length with repeated characters in a given string. We are allowed to perform one swap operation on any two characters in the string.

To understand this, let's consider an example:

• text = "ababa"
• We can make one swap of 'b' with 'a'. The string becomes "aaaab" after swapping first 'b' with last 'a'.
• Now, the longest substring with repeating characters is "aaa" and its length is 3. So, the output is 3.

This problem can be solved using Greedy approach, where we try to extend the count of each repeated characters to its next block (group). If the next block is only string.length() away, we need an extra character. If it's not possible to get an extra character, we can only extend the count to its next group if the count of next group is 1 and the next character of the next group is the same.

Solution Approach

The basic idea is to first count the frequency of each character. We then loop through each character group. A group is a substring where the same characters are adjacent and count the length of each group.

We use the greedy approach to calculate the maximum length of repeated characters by swapping with the next group. The condition is that if the length of the next group is 1 and the next character of the next group is the same. The maximum length is then the minimum of the sum of current group and next group length plus 1 and character count in the string.

Let's illustrate this with an example:

• text = "aaabaaa"
• Character count: {'a': 6, 'b': 1}
• Groups: [('a', 3), ('b', 1), ('a', 3)]
• For each group, ans = max(ans, min(length + 1, count[c - 'a'])) = max(0, min(3+1, 6)) = 4
• For middle groups, if groups[i - 1].first == groups[i + 1].first and groups[i].second == 1, then ans = max(ans, min(groups[i - 1].second + groups[i + 1].second + 1, count[groups[i - 1].first - 'a'])) = max(4, min(3+3+1, 6)) = max(4, 6) = 6
• Output: 6

Python Solution

1
2python
3class Solution:
4    def maxRepOpt1(self, text: str) -> int:
5        count = [0]*26
6        for c in text:
7            count[ord(c) - ord('a')] += 1
8        res = 0
9        i = 0
10        while i < len(text):
11            c = text[i]
12            j = i
13            while j < len(text) and text[j] == c: j += 1
14            next = j
15            while next < len(text) - 1 and text[next] != c and text[next+1] == c: next += 1
16            length = next - i + 1
17            res = max(res, min(length, count[ord(c) - ord('a')]))
18            i = j
19        return res

Java Solution

1
2java
3class Solution {
4    public int maxRepOpt1(String text) {
5        int[] count = new int[26];
6        for (char c : text.toCharArray())
7            count[c - 'a']++;
8        int maxLen = 0;
9        for (int i = 0; i < text.length();) {
10            char c = text.charAt(i);
11            int j = i;
12            while (j < text.length() && text.charAt(j) == c) j++;
13            int next = j;
14            while (next < text.length() - 1 && text.charAt(next) != c && text.charAt(next+1) == c) next++;
15            int length = next - i + 1;
16            maxLen = Math.max(maxLen, Math.min(length, count[c - 'a']));
17            i = j;
18        }
19        return maxLen;
20    }
21}

JavaScript Solution

1
2javascript
3var maxRepOpt1 = function(text) {
4    let count = new Array(26).fill(0);
5    for(let c of text) {
6        count[c.charCodeAt() - 97]++;
7    }
8
9    let maxLen = 0;
10    for (let i = 0; i < text.length;) {
11        let c = text[i];
12        let j = i;
13        while (j < text.length && text[j] === c) j++;
14        let k = j;
15        while (k < text.length - 1 && text.charAt(k) !== c && text.charAt(k+1) === c) k++;
16        let len = k - i + 1;
17        maxLen = Math.max(maxLen, Math.min(len, count[c.charCodeAt() - 97]));
18        i = j;
19    }
20    return maxLen;
21};

C++ Solution

1
2c++
3class Solution {
4public:
5    int maxRepOpt1(string text) {
6        int count[26] = {0};
7        for (char c : text)
8            count[c - 'a']++;
9        int maxLen = 0;
10        for (int i = 0; i < text.size();) {
11            char c = text[i];
12            int j = i;
13            while (j < text.size() && text[j] == c) j++;
14            int next = j;
15            while (next < text.size() - 1 && text[next] != c && text[next+1] == c) next++;
16            int length = next - i + 1;
17            maxLen = max(maxLen, min(length, count[c - 'a']));
18            i = j;
19        }
20        return maxLen;
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxRepOpt1(string text) {
5        int[] count = new int[26];
6        foreach (char c in text)
7            count[c - 'a']++;
8        int maxLen = 0;
9        for (int i = 0; i < text.Length;) {
10            char c = text[i];
11            int j = i;
12            while (j < text.Length && text[j] == c) j++;
13            int next = j;
14            while (next < text.Length - 1 && text[next] != c && text[next+1] == c) next++;
15            int length = next - i + 1;
16            maxLen = Math.Max(maxLen, Math.Min(length, count[c - 'a']));
17            i = j;
18        }
19        return maxLen;
20    }
21}

In all the implementations above, we first initialize a count array to keep the count of each character in the string. Then we loop through the string to find the groups and calculate the maximum length of repeated character with one possible swap.Let's summarise our approach and conclude this.

Conclusion

In this problem, we used a greedy approach to solve the problem of finding the longest substring length with repeated characters. We used a frequency count and then groups of repeating characters to calculate the maximum length possible with one swap. As we iterate through the string, we consider each group of repeating characters at a time and calculate the length of the repeated character we can make by swapping one character. This length is limited by the frequency count that was calculated initially to prevent swapping with characters not present in the string.

We then update our maximum length achieved so far. We continue this until the end of the string and finally, the maximum length achieved will be our answer.

Please remember that this approach assumes that we can only swap adjacent characters.

This solution works with a runtime complexity of O(n) and space complexity of O(1) because we use a fixed amount of space to store the count of characters in the string.

The code has been provided in Python, Java, JavaScript, C++, and C#, providing a wide range of the implementation of the same concept and the approach in different programming languages.