LeetCode Solutions Blog

Swap For Longest Repeated Character Substring

Number: 1261

Difficulty: Medium

Paid? No

Problem Description

Given a string text, you are allowed to swap two characters in the string exactly once. Determine the length of the longest substring that can be formed consisting of one repeated character, after performing at most one swap.

Key Insights

Count the frequency of each character.
Split the string into groups of consecutive identical characters.
For each group, consider extending its length by swapping a character from elsewhere (if additional occurrences exist).
Check for the case where two groups of the same character are separated by exactly one different character; if so, merging them (with a swap) might yield a longer repeated substring.
Use a greedy approach to iterate through the groups and update the maximum achievable length.

Space and Time Complexity

Time Complexity: O(n) because we traverse the string to group characters and iterate over groups. Space Complexity: O(n) in the worst-case scenario (when the string has alternating characters) for storing groups and frequency counts.

Solution

The solution uses a two-step process:

First, count the total occurrences of each character.
Second, create a list of groups where each group contains a character and its consecutive count. Then, for each group, determine the maximum length achievable by:
- Using a swap to extend the current group if there are additional characters available elsewhere.
- Merging two adjacent groups of the same character when they are separated by exactly one different character.

The algorithm then iterates through all groups and maintains the maximum length found.

Code Solutions

# Python solution for Swap For Longest Repeated Character Substring

def maxRepOpt1(text: str) -> int:
    # Count total frequency for each character in text
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1

    # Create groups: list of tuples (character, count)
    groups = []
    i = 0
    n = len(text)
    while i < n:
        ch = text[i]
        count = 0
        while i < n and text[i] == ch:
            count += 1
            i += 1
        groups.append((ch, count))
    
    max_length = 0
    # Iterate over groups to determine maximum substring length after one swap
    for idx, (ch, count) in enumerate(groups):
        # Calculate potential length if we extend the current block with one more same letter from elsewhere.
        current_max = count
        if freq[ch] > count:
            current_max = count + 1

        # Check if merging with a non adjacent group is possible,
        # i.e., if there is exactly one different char between two groups of same character.
        if idx + 2 < len(groups) and groups[idx + 1][1] == 1 and groups[idx + 2][0] == ch:
            merged = groups[idx][1] + groups[idx + 2][1]
            # If there is an extra occurrence of ch elsewhere, add one
            if freq[ch] > merged:
                merged += 1
            current_max = max(current_max, merged)
        
        max_length = max(max_length, current_max)
    
    return max_length

# Example usage:
print(maxRepOpt1("ababa"))   # Expected output: 3
print(maxRepOpt1("aaabaaa")) # Expected output: 6
print(maxRepOpt1("aaaaa"))   # Expected output: 5