{x}
blog image

Swap For Longest Repeated Character Substring

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.

 

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.

 

Constraints:

  • 1 <= text.length <= 2 * 104
  • text consist of lowercase English characters only.

Solution Explanation: Swap For Longest Repeated Character Substring

This problem asks us to find the length of the longest substring containing only repeated characters after performing at most one swap of characters within the input string.

Approach:

The solution uses a two-pointer sliding window approach combined with a frequency count of characters. The core idea is to iterate through the string, identifying consecutive runs of the same character. For each run:

  1. Identify the run: The j pointer finds the end of a consecutive run of the same character starting at i.
  2. Extend with potential swaps: The k pointer finds a subsequent run of the same character. This is where the potential swap comes into play. We could potentially extend the initial run (l length) by including this subsequent run (r length) if the count of that character allows it.
  3. Update the maximum length: The maximum length is updated considering both the combined lengths of consecutive runs and the overall frequency of the character. We take the minimum because we can only extend the current run by at most the number of available characters of that type (to avoid exceeding the total count).

Time Complexity Analysis:

The outer loop iterates through the string once (O(n)), and the inner loops (j and k) also move through the string linearly. Thus, the overall time complexity is O(n), which is linear in the length of the string.

Space Complexity Analysis:

We use a cnt array (or hash map) to store the frequency count of each character. The size of this array is fixed (26 for lowercase English letters). Therefore, the space complexity is O(1), which is constant. The space usage doesn't depend on the input string length.

Code Explanation (Python):

from collections import Counter
 
class Solution:
    def maxRepOpt1(self, text: str) -> int:
        cnt = Counter(text)  # Count character frequencies
        n = len(text)
        ans = i = 0
        while i < n:
            j = i
            while j < n and text[j] == text[i]: #Find the end of consecutive run
                j += 1
            l = j - i  # Length of current run
 
            k = j + 1
            while k < n and text[k] == text[i]: #Find the next consecutive run of same char
                k += 1
            r = k - j - 1  # Length of subsequent run
 
            ans = max(ans, min(l + r + 1, cnt[text[i]])) #Update max length: min(combined, available count)
            i = j  # Move to the next character
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, implementing the same algorithm with appropriate syntax changes for each language. The core logic remains the same: two-pointer sliding window for run identification and frequency count to limit potential extensions.