LeetCode 1156 - Swap For Longest Repeated Character Substring

LeetCode Problem 1156

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem asks us to determine the length of the longest substring in a given string text where all characters are the same, and we are allowed to swap exactly two characters in the string. The swap can be between any two characters, not necessarily adjacent, but we are limited to a single swap per evaluation. The input text is a string of lowercase English letters, with a length up to 2 * 10^4. The output is an integer representing the maximum length of a substring consisting of repeated characters after the optimal swap.

The constraints indicate that text can be fairly long, so a naive approach that examines all possible swaps is computationally infeasible. Important edge cases include strings that are already uniform (e.g., "aaaaa"), strings with only two characters alternating (e.g., "ababab"), or strings where the optimal swap does not immediately combine adjacent groups of characters.

We need to consider the frequency of each character and the gaps between repeated character blocks. The key observation is that we may only need to merge two blocks of the same character separated by a single different character, and at most one swap is allowed, potentially leveraging other occurrences of that character elsewhere in the string.

Approaches

The brute-force approach would try every possible swap of two characters, recompute the length of the longest repeated-character substring, and keep track of the maximum. While this guarantees the correct answer, it is highly inefficient because there are O(n^2) possible swaps and evaluating each substring is O(n), leading to O(n^3) time complexity. For n up to 2 * 10^4, this is not feasible.

The optimal approach relies on grouping consecutive identical characters and analyzing opportunities to extend these groups by either swapping with other instances of the same character or merging blocks separated by a single different character. The main steps are to identify character blocks, count total occurrences of each character, and examine each block to determine the maximum extended length achievable with one swap.

Algorithm Walkthrough

1. Traverse the string text and create a list of blocks where each block represents a consecutive sequence of the same character. Each block stores the character, its start index, and its length.
2. Create a frequency map of the total occurrences of each character in the entire string. This helps to check if there are additional instances of a character to swap in.
3. Initialize a variable max_len to store the maximum repeated substring length found.
4. Iterate through each block and compute two possible extensions:

• Extension within the same block: The length of the current block can be increased by 1 if there exists at least one more occurrence of the same character elsewhere in the string (from the frequency map), allowing a swap.
• Merge across a single-character gap: If a block is separated from another block of the same character by exactly one different character, consider merging them. The merged length can be increased by 1 if additional instances of the character exist elsewhere.

5. Update max_len for each evaluated scenario.
6. Return max_len.

Why it works: By grouping consecutive identical characters and using character frequency information, we efficiently capture all opportunities to extend repeated-character substrings. We either extend within a block or merge across a one-character gap, ensuring we consider all valid swaps. Since we only examine each block and its neighbors, the algorithm runs linearly with respect to string length.

Python Solution

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        from collections import Counter

        n = len(text)
        if n == 1:
            return 1

        # Step 1: Count total occurrences of each character
        freq = Counter(text)

        # Step 2: Create blocks of consecutive characters
        blocks = []
        i = 0
        while i < n:
            char = text[i]
            start = i
            while i < n and text[i] == char:
                i += 1
            blocks.append((char, start, i - start))  # (character, start index, length)

        max_len = 0

        # Step 3: Evaluate each block
        for j, (char, start, length) in enumerate(blocks):
            # Option 1: Extend block with another occurrence of same char
            if freq[char] > length:
                max_len = max(max_len, length + 1)
            else:
                max_len = max(max_len, length)

            # Option 2: Merge with block two positions away if separated by one different char
            if j > 0 and j < len(blocks) - 1:
                prev_char, _, prev_len = blocks[j - 1]
                next_char, _, next_len = blocks[j + 1]
                if prev_char == next_char and length == 1 and prev_char == char:
                    continue  # single-char block not matching the previous, skip
                if prev_char == next_char and length == 1 and prev_char == char:
                    continue
                if prev_char == next_char and length == 1:
                    merged_len = prev_len + next_len
                    # Can we swap one more char in?
                    if freq[prev_char] > merged_len:
                        merged_len += 1
                    max_len = max(max_len, merged_len)

            # Option 3: Merge with next block if same char
            if j < len(blocks) - 1:
                next_char, _, next_len = blocks[j + 1]
                if next_char == char:
                    merged_len = length + next_len
                    if freq[char] > merged_len:
                        merged_len += 1
                    max_len = max(max_len, merged_len)

        return max_len

Implementation Walkthrough: The solution first counts total character occurrences, then constructs blocks of consecutive identical characters. It iterates over each block to consider either extending it using a swap or merging with neighboring blocks if separated by a single different character. The result is tracked in max_len.

Go Solution

func maxRepOpt1(text string) int {
    n := len(text)
    if n == 1 {
        return 1
    }

    freq := make(map[byte]int)
    for i := 0; i < n; i++ {
        freq[text[i]]++
    }

    type block struct {
        char  byte
        start int
        length int
    }

    var blocks []block
    i := 0
    for i < n {
        ch := text[i]
        start := i
        for i < n && text[i] == ch {
            i++
        }
        blocks = append(blocks, block{ch, start, i - start})
    }

    maxLen := 0
    for j := 0; j < len(blocks); j++ {
        ch := blocks[j].char
        length := blocks[j].length

        if freq[ch] > length {
            maxLen = max(maxLen, length+1)
        } else {
            maxLen = max(maxLen, length)
        }

        if j > 0 && j < len(blocks)-1 && blocks[j].length == 1 {
            if blocks[j-1].char == blocks[j+1].char {
                mergedLen := blocks[j-1].length + blocks[j+1].length
                if freq[blocks[j-1].char] > mergedLen {
                    mergedLen++
                }
                maxLen = max(maxLen, mergedLen)
            }
        }

        if j < len(blocks)-1 && blocks[j+1].char == ch {
            mergedLen := length + blocks[j+1].length
            if freq[ch] > mergedLen {
                mergedLen++
            }
            maxLen = max(maxLen, mergedLen)
        }
    }

    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go Notes: The Go implementation mirrors the Python approach. Maps are used for frequency counts. A struct block represents consecutive character sequences. Slice indexing handles neighbors safely, and a helper max function replaces Python's built-in max.

Worked Examples

Example 1: "ababa"

Example 2: "aaabaaa"