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;
    }
}

All Problems

All Solutions