Welcome to Subscribe On Youtube
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 <= 20000textconsist 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; } } -
// OJ: https://leetcode.com/problems/swap-for-longest-repeated-character-substring/ // Time: O(N) // Space: O(1) class Solution { int cnt[26] = {}; int maxRep(string &s, char c) { int ans = 0, prev = -1, mid = -1; for (int i = 0; i <= s.size(); ++i) { if (i < s.size() && s[i] == c) continue; int len = i - prev - 1; if (mid != -1 && len - 1 == cnt[c - 'a']) --len; ans = max(ans, len); prev = mid; mid = i; } return ans; } public: int maxRepOpt1(string s) { int ans = 0; for (char c : s) cnt[c - 'a']++; for (char c = 'a'; c <= 'z'; ++c) { ans = max(ans, maxRep(s, c)); } return ans; } }; -
class Solution: def maxRepOpt1(self, text: str) -> int: cnt = Counter(text) n = len(text) ans = i = 0 while i < n: j = i while j < n and text[j] == text[i]: j += 1 l = j - i k = j + 1 while k < n and text[k] == text[i]: k += 1 r = k - j - 1 ans = max(ans, min(l + r + 1, cnt[text[i]])) i = j return ans ############ # 1156. Swap For Longest Repeated Character Substring # https://leetcode.com/problems/swap-for-longest-repeated-character-substring/ class Solution: def maxRepOpt1(self, text: str) -> int: A = [[c, len(list(x))] for c,x in itertools.groupby(text)] count = collections.Counter(text) res = max(min(count[c], x + 1) for c,x in A) for i in range(1, len(A) - 1): if A[i - 1][0] == A[i + 1][0] and A[i][1] == 1: res = max(res, min(A[i - 1][1] + A[i + 1][1] + 1, count[A[i - 1][0]])) return res