Formatted question description: https://leetcode.ca/all/1156.html

# 1156. Swap For Longest Repeated Character Substring

## Level

Medium

## Description

Given a string `text`

, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

**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”, which its length is 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”, which its length is 6.

**Example 3:**

**Input:** text = “aaabbaaa”

**Output:** 4

**Example 4:**

**Input:** text = “aaaaa”

**Output:** 5

**Explanation:** No need to swap, longest repeated character substring is “aaaaa”, length is 5.

**Example 5:**

**Input:** text = “abcdef”

**Output:** 1

**Constraints:**

`1 <= text.length <= 20000`

`text`

consist of lowercase English characters only.

## Solution

Since `text`

consists of lowercase English letters, for each lowercase letter, obtain the intervals in `text`

. An interval represents the indices range of a substring which contains repeated letters, where each substring is the longest possible (which means increasing the length of the substring by 1 will introduce a different letter). The intervals are obtained by looping over `text`

.

After the intervals are obtained, for each letter, obtain all the intervals and calculate the maximum length. If a letter has only one interval, then the maximum length is the length of the interval. If a letter has two intervals, then the maximum length is the sum of the two intervals’ lengths if the two intervals have distance 1 (which means there is one different letter between two intervals), or the length of the longer interval plus 1 otherwise. If a letter has three or more intervals, then each time check the two adjacent intervals, and the maximum length is the sum of the two intervals’ lengths plus 1 if the two intervals have distance 1 (which means there is one different letter between two intervals), or the length of the longer interval plus 1 otherwise.

Finally, return the maximum length.

```
class Solution {
public int maxRepOpt1(String text) {
List<int[]>[] intervals = new List[26];
for (int i = 0; i < 26; i++)
intervals[i] = new ArrayList<int[]>();
char prevChar = 0;
int begin = 0, end = 0;
char[] array = text.toCharArray();
int length = array.length;
for (int i = 0; i < length; i++) {
char c = array[i];
if (c != prevChar) {
if (prevChar != 0) {
int index = prevChar - 'a';
end = i - 1;
int[] interval = new int[2];
interval[0] = begin;
interval[1] = end;
intervals[index].add(interval);
}
begin = i;
end = i;
} else
end = i;
prevChar = c;
}
int lastIndex = prevChar - 'a';
int[] lastInterval = new int[2];
lastInterval[0] = begin;
lastInterval[1] = end;
intervals[lastIndex].add(lastInterval);
int max = 1;
for (int i = 0; i < 26; i++) {
List<int[]> currentIntervals = intervals[i];
int size = currentIntervals.size();
int currentMax = 1;
if (size == 1) {
int[] currentInterval = currentIntervals.get(0);
int currentLength = currentInterval[1] - currentInterval[0] + 1;
currentMax = Math.max(currentMax, currentLength);
} else if (size == 2) {
int[] currentInterval0 = currentIntervals.get(0);
int[] currentInterval1 = currentIntervals.get(1);
if (currentInterval1[0] - currentInterval0[1] == 2) {
int currentLength = currentInterval0[1] - currentInterval0[0] + 1 + currentInterval1[1] - currentInterval1[0] + 1;
currentMax = Math.max(currentMax, currentLength);
} else {
int currentLength = Math.max(currentInterval0[1] - currentInterval0[0] + 1, currentInterval1[1] - currentInterval1[0] + 1) + 1;
currentMax = Math.max(currentMax, currentLength);
}
} else {
for (int j = 1; j < size; j++) {
int[] currentInterval0 = currentIntervals.get(j - 1);
int[] currentInterval1 = currentIntervals.get(j);
if (currentInterval1[0] - currentInterval0[1] == 2) {
int currentLength = currentInterval0[1] - currentInterval0[0] + 1 + currentInterval1[1] - currentInterval1[0] + 1 + 1;
currentMax = Math.max(currentMax, currentLength);
} else {
int currentLength = Math.max(currentInterval0[1] - currentInterval0[0] + 1, currentInterval1[1] - currentInterval1[0] + 1) + 1;
currentMax = Math.max(currentMax, currentLength);
}
}
}
max = Math.max(max, currentMax);
}
return max;
}
}
```