Introduction

In this blog post, we will explore how to solve the LeetCode problem "1156" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: text = "ababa" Output: 3 Explanation: 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 Explanation: 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 Explanation: 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.

Explanation

Here's the breakdown of the solution:

• Iterate through distinct characters: The core idea is to iterate through each distinct character present in the input string. For each character, we'll try to maximize the length of the longest substring consisting of that character after performing at most one swap.
• Sliding Window Approach: For each character, employ a sliding window technique. Expand the window until you encounter more than one character that is not the target character. Once you've reached this limit, try to find a suitable position outside of the current window to swap with one of the non-target characters within the window. If a swap increases the window size and creates a longer repeated character substring, keep track of the maximum length found.

• Count and Swap: Count the occurrences of each character in the string. The maximum length achievable with swaps is limited by the total count of the character. If the length calculated via the sliding window is more than total count of the target char, then return the total count.

• Time Complexity: O(26*N) which is O(N), where N is the length of the string. Space Complexity: O(1).

Code

    def longest_repeating_substring_after_swap(text: str) -> int:
    """
    Finds the length of the longest substring with repeated characters after swapping at most two characters.
    """
    n = len(text)
    max_len = 0

    for char in set(text):
        count = text.count(char)
        left = 0
        diff_count = 0
        for right in range(n):
            if text[right] != char:
                diff_count += 1

            while diff_count > 1:
                if text[left] != char:
                    diff_count -= 1
                left += 1

            max_len = max(max_len, right - left + 1)

        max_len = min(max_len, count)

    return max_len