We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Swap For Longest Repeated Character Substring

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem allows for one swap of characters, which can potentially maximize the length of a substring with repeated characters.
  • The solution involves identifying the most frequent character and calculating how many of that character can be made contiguous with one swap.
  • The sliding window technique can be employed to efficiently find the longest substring while keeping track of character counts.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use the sliding window technique along with a frequency count of characters. The idea is to maintain a window of characters such that we can determine the maximum length of the substring consisting of the same character after allowing for one swap. We keep track of the maximum frequency of any character within the current window and adjust the window size accordingly to ensure that the total characters in the window minus the maximum frequency does not exceed 1 (the one character we can swap).

Code Solutions

def maxRepOpt1(text: str) -> int:
    char_count = {}
    max_length = 0
    left = 0
    max_freq = 0

    # Count the frequency of each character
    for char in text:
        char_count[char] = char_count.get(char, 0) + 1

    for right in range(len(text)):
        max_freq = max(max_freq, char_count[text[right]])

        # If the window size minus the max frequency exceeds 1, shrink the window
        while (right - left + 1) - max_freq > 1:
            char_count[text[left]] -= 1
            left += 1

        # Calculate the maximum length accounting for any swaps
        max_length = max(max_length, right - left + 1)

    # We can swap at most once, check if we can include one more character
    for count in char_count.values():
        if count > max_freq:
            max_length = min(max_length + 1, len(text))

    return max_length
← Back to All Questions