#1156

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Swap For Longest Repeated Character Substring

Find the maximum length of a repeated character substring after swapping two characters using a sliding window approach with hash tracking.

hash table string sliding window

Problem Statement

Given a string text consisting of lowercase English letters, you can swap any two characters in the string at most once. Determine the maximum length of a substring containing the same repeated character that can result from such a swap.

For example, if text = "ababa", swapping the first 'b' with the last 'a' produces "aaaba", yielding a repeated substring "aaa" of length 3. Your task is to return this maximum possible length for any valid swap.

Examples

Example 1

Input: text = "ababa"

Output: 3

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

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

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 Approach

Run-Length Encoding

Convert the string into blocks of consecutive identical characters, recording both character and block length. This enables quick access to block sizes for evaluating swap impact.

Sliding Window Merge

Use a sliding window over the blocks to consider merging two same-character blocks separated by a single different character. Track counts to determine if a swap can increase the merged length.

Use Character Frequency Map

Maintain a hash map of character frequencies to ensure that swaps are valid. This helps to check whether additional occurrences of a character exist to perform a swap that extends the repeated substring.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed in run-length encoding and during the sliding window merge. Space complexity is O(n) for storing blocks and O(1) for the fixed alphabet frequency map.

What Interviewers Usually Probe

Check if the candidate identifies that only one swap is allowed and explains its effect on repeated substrings.
Look for recognition that blocks of the same character separated by one different character can be merged strategically.
Listen for a plan that uses linear scanning or sliding window rather than brute force substring checks.

Common Pitfalls or Variants

Common pitfalls

Failing to consider merging non-contiguous blocks separated by a single character.
Ignoring the case when all characters are identical and no swap is needed.
Overcomplicating the solution with nested loops instead of using run-length encoding and sliding window.

Follow-up variants

Allow multiple swaps and compute the longest repeated substring achievable with k swaps.
Return the starting and ending indices of the maximum repeated substring after one swap.
Compute the longest repeated substring after swaps for uppercase and lowercase characters with different case sensitivity rules.

FAQ

What is the optimal strategy for 'Swap For Longest Repeated Character Substring'?

Use run-length encoding to segment consecutive characters, then slide a window to merge blocks separated by one different character, considering frequency counts for swap validity.

Can this problem be solved without a sliding window?

Direct brute force is possible but inefficient; sliding window plus run-length encoding is preferred to handle large inputs within linear time.

How do you handle strings where all characters are the same?

No swap is needed; the maximum repeated substring length is the length of the string itself.

Does the frequency of each character matter?

Yes, maintaining a character frequency map ensures that a swap is valid and helps determine whether isolated blocks can be extended.

Is run-length encoding always necessary for this problem pattern?

It is highly recommended for 'Sliding window with running state updates' as it efficiently represents consecutive character blocks and simplifies merge calculations.

terminal

Solution

Solution 1: Two Pointers

First, we use a hash table or array $cnt$ to count the occurrence of each character in the string $text$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#1016 binary string with substrings representing 1 to n #1297 maximum number of occurrences of a substring #1358 number of substrings containing all three characters