Problem Description

You are given a string text consisting of characters. You can perform at most one swap operation where you choose any two characters in the string and exchange their positions.

Your task is to find the length of the longest possible substring that contains only repeated characters (all characters in the substring are the same) after performing at most one swap.

For example, if you have the string "ababa", you could swap the character at position 1 ('b') with the character at position 2 ('a') to get "aaabb". This would give you a substring "aaa" of length 3 with repeated characters.

The key insight is that you want to maximize the length of consecutive identical characters by potentially swapping one character from elsewhere in the string to extend or connect groups of the same character.

The algorithm works by examining each group of consecutive identical characters and checking if it can be extended by:

1. Adding one more character of the same type from elsewhere in the string
2. Connecting it with another group of the same character that's separated by exactly one different character (by swapping that different character out)

The maximum possible length for any character c is limited by the total count of that character in the entire string, since you cannot create more instances of a character than what exists in the original string.

Intuition

When we think about maximizing the length of repeated characters with one swap, we need to consider what patterns we can create or extend through swapping.

Let's think about the possible scenarios where a swap would be beneficial:

1. Extending a group: If we have a group like "aaa" and there's another 'a' somewhere else in the string, we can swap that 'a' to be adjacent to our group, making it "aaaa".

2. Bridging two groups: If we have two groups of the same character separated by a single different character, like "aaa_b_aa", we can swap that 'b' with an 'a' from elsewhere (if available) to create "aaaaaa".

3. Filling a gap: Similar to bridging, but we might have "aa_b_a" and swap the 'b' out to connect them.

The key observation is that for any character, we want to find segments of consecutive occurrences and see if we can make them longer. When we encounter a segment like "aaa", we should check:

• Is there another segment of 'a' characters nearby (separated by just one different character)?
• If yes, can we connect them by swapping out the separating character?
• If no nearby segment exists, can we at least add one more 'a' from elsewhere?

The crucial constraint is that we cannot create more of any character than what originally exists in the string. If we have only 5 'a' characters total in the string, the maximum length of consecutive 'a's we can achieve is 5, regardless of how we swap.

This leads us to a two-pointer approach: for each position, we find the current segment of identical characters, then look ahead to see if there's another segment of the same character just one position away. The maximum achievable length would be min(left_segment + right_segment + 1, total_count_of_that_character).

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a two-pointer technique to efficiently find all segments of repeated characters and determine the maximum possible length after one swap.

First, we count the frequency of each character in the string using a Counter: cnt = Counter(text). This gives us the total occurrences of each character, which serves as an upper bound for the maximum possible length of any repeated character substring.

The main algorithm uses three pointers: i, j, and k:

1. Finding the left segment: Starting from position i, we move pointer j to the right while text[j] == text[i]. This gives us a segment of length l = j - i where all characters are the same as text[i].

2. Skipping the gap: After finding the left segment, position j points to a different character. We skip this character and set k = j + 1.

3. Finding the right segment: We continue moving k to the right while text[k] == text[i]. This gives us another segment of the same character with length r = k - j - 1 (we subtract 1 because there's a gap character at position j).

4. Calculating maximum length: For the current character text[i], the maximum achievable length is:

   • If we can bridge the two segments by swapping the gap character: l + r + 1
   • But this is limited by the total count of that character: min(l + r + 1, cnt[text[i]])

   The +1 accounts for either:

   • Swapping the gap character at position j with another instance of text[i] from elsewhere
   • Or if no right segment exists (r = 0), adding one more character of the same type to extend the left segment

5. Moving to next segment: We update i = j to move to the next different character segment and repeat the process.

The algorithm continues until we've examined all positions in the string, keeping track of the maximum length found across all segments.

Time Complexity: O(n) where n is the length of the string, as each character is visited at most twice.

Space Complexity: O(1) or O(26) for the character counter (assuming lowercase English letters).

Example Walkthrough

Let's walk through the algorithm with the string text = "ababa".

Step 1: Count character frequencies

• cnt = {'a': 3, 'b': 2}
• This tells us the maximum possible length for 'a' is 3 and for 'b' is 2.

Step 2: Process segments starting from position 0

Iteration 1: i = 0

• Current character: text[0] = 'a'
• Find left segment: j moves from 0 to 1 (stops at 'b')
  • Left segment = "a", length l = 1 - 0 = 1
• Skip gap: k = j + 1 = 2
• Find right segment: k moves from 2 to 3 (text[2] = 'a', stops at text[3] = 'b')
  • Right segment = "a", length r = 3 - 1 - 1 = 1
• Calculate max: min(1 + 1 + 1, cnt['a']) = min(3, 3) = 3
  • This represents swapping the 'b' at position 1 with an 'a' from position 4
• Update: i = j = 1, ans = 3

Iteration 2: i = 1

• Current character: text[1] = 'b'
• Find left segment: j moves from 1 to 2 (stops at 'a')
  • Left segment = "b", length l = 2 - 1 = 1
• Skip gap: k = j + 1 = 3
• Find right segment: k moves from 3 to 4 (text[3] = 'b', stops at text[4] = 'a')
  • Right segment = "b", length r = 4 - 2 - 1 = 1
• Calculate max: min(1 + 1 + 1, cnt['b']) = min(3, 2) = 2
  • Limited by total count of 'b' (only 2 'b's exist)
• Update: i = j = 2, ans = max(3, 2) = 3

Iteration 3: i = 2

• Current character: text[2] = 'a'
• Find left segment: j moves from 2 to 3 (stops at 'b')
  • Left segment = "a", length l = 3 - 2 = 1
• Skip gap: k = j + 1 = 4
• Find right segment: k moves from 4 to 5 (text[4] = 'a', reaches end)
  • Right segment = "a", length r = 5 - 3 - 1 = 1
• Calculate max: min(1 + 1 + 1, cnt['a']) = min(3, 3) = 3
• Update: i = j = 3, ans = max(3, 3) = 3

Iteration 4: i = 3

• Current character: text[3] = 'b'
• Find left segment: j moves from 3 to 4 (stops at 'a')
  • Left segment = "b", length l = 4 - 3 = 1
• Skip gap: k = j + 1 = 5 (out of bounds)
• Find right segment: No right segment, r = 0
• Calculate max: min(1 + 0 + 1, cnt['b']) = min(2, 2) = 2
  • The +1 represents adding another 'b' from position 1 to extend
• Update: i = j = 4, ans = max(3, 2) = 3

Iteration 5: i = 4

• Current character: text[4] = 'a'
• Find left segment: j moves from 4 to 5 (reaches end)
  • Left segment = "a", length l = 5 - 4 = 1
• No gap or right segment
• Calculate max: min(1 + 0 + 1, cnt['a']) = min(2, 3) = 2
• Update: i = j = 5, loop ends

Result: Maximum length = 3

This can be achieved by swapping text[1] with text[4], transforming "ababa" → "aaabb", creating "aaa" of length 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a single main loop with variable i that traverses the string. Within each iteration:

• The inner while loop with variable j finds the end of the current consecutive segment
• The second inner while loop with variable k checks for matching characters after a gap

Although there are nested loops, each character in the string is visited at most twice (once by the j pointer and potentially once by the k pointer). The key observation is that i jumps directly to j after each iteration, meaning we don't revisit characters. Therefore, the amortized time complexity is O(n) where n is the length of the string.

Space Complexity: O(C)

The space is primarily used by the Counter object which stores the frequency of each unique character in the string. Since the problem deals with lowercase English letters, the maximum number of unique characters is 26. Therefore, the space complexity is O(C) where C = 26, which represents the size of the character set.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly handling single character groups

A common mistake is assuming there's always a right group after the gap. When we have a pattern like "aabaa" and we're at the last group of 'a', there's no right group, so right_group_length = 0. The code correctly handles this by using k - j - 1, which naturally gives 0 when k = j + 1.

2. Forgetting the character count constraint

A critical pitfall is calculating left + right + 1 without considering the total count limitation. For example, in "aabaaa", when examining the first group of 'a', we might think we can achieve length 6 (2 + 3 + 1), but we only have 5 'a's total. Always cap the result with min(..., char_count[text[i]]).

3. Off-by-one errors in length calculations

When calculating right_group_length, it's easy to make mistakes with the formula. Remember:

• left_group_length = j - i (straightforward)
• right_group_length = k - j - 1 (we subtract 1 for the gap character at position j)

Getting this wrong would incorrectly count the gap character as part of the right group.

4. Not handling edge cases properly

• Single character string: The code handles this correctly since the while loops naturally terminate
• String with all same characters: Like "aaaa", the maximum should be 4, not 5
• No possible swap benefit: Like "abcdef", each character appears once, so max length is 1

5. Misunderstanding the "+1" in the formula

The +1 in left + right + 1 represents either:

• A character from elsewhere being swapped into the gap position (when connecting two groups)
• An additional character of the same type being swapped adjacent to a single group (when extending)

It does NOT mean we're creating a new character out of nowhere.

Solution to Avoid These Pitfalls:

# Add explicit comments and assertions to clarify logic
def maxRepOpt1(self, text: str) -> int:
    char_count = Counter(text)
    n = len(text)
    max_length = 0
    i = 0
  
    while i < n:
        # Find left group
        j = i
        while j < n and text[j] == text[i]:
            j += 1
        left_group_length = j - i
      
        # Find right group (may not exist)
        k = j + 1  # Skip the gap character at position j
        while k < n and text[k] == text[i]:
            k += 1
      
        # Calculate right group length
        # If no right group exists, this will be 0
        right_group_length = max(0, k - j - 1)  # Explicit max for clarity
      
        # The +1 accounts for swapping in one character
        # But we can't exceed total count of this character
        max_possible = min(
            left_group_length + right_group_length + 1,
            char_count[text[i]]
        )
      
        max_length = max(max_length, max_possible)
        i = j
      
    return max_length