Swap For Longest Repeated Character Substring

Swap For Longest Repeated Character Substring - Problem

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.

A substring is a contiguous sequence of characters within a string. After swapping two characters, you need to find the longest substring where all characters are the same.

Input & Output

Example 1 — Basic Case

$ Input: text = "ababa"

› Output: 3

💡 Note: We can swap the second 'b' with the last 'a' to get "aabaa", then the longest substring with repeated characters is "aaa" with length 3.

Example 2 — All Same Characters

$ Input: text = "aaaa"

› Output: 4

💡 Note: All characters are already the same, so no swap is needed. The entire string "aaaa" has length 4.

Example 3 — Two Different Characters

$ Input: text = "abab"

› Output: 3

💡 Note: We can swap one 'b' with one 'a' to get "aaab" or "abaa", giving us a longest repeated substring of length 3.

Constraints

1 ≤ text.length ≤ 1000
text consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String "ababa" - need to find best swap

Process

Try swapping characters to maximize repeated substring

Output

Return length 3 (longest possible after one swap)

Key Takeaway

🎯 Key Insight: Use sliding window to find longest substring with at most one character different from target

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is that we need to find the longest substring that can be made uniform with exactly one character swap. The optimal approach uses sliding window for each unique character to find the longest substring with at most one mismatch. Time: O(26n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Character Frequency	O(26n)	O(1)	For each character, use sliding window to find longest substring with at most one mismatch
Brute Force - Try All Swaps	O(n⁴)	O(n)	Try every possible swap and find the longest repeated substring for each

Sliding Window with Character Frequency — Algorithm Steps

Count frequency of each character
For each character type, use sliding window
Expand window while counting mismatches
If mismatches > 1, shrink window from left
Track maximum window size across all characters

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Target

Try each unique character as target

Sliding Window

Expand window while mismatches ≤ 1

Max Length

Return the maximum window size found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxLengthForChar(const char* s, char targetChar) {
    int n = strlen(s);
    int left = 0;
    int maxLen = 0;
    int mismatches = 0;
    
    for (int right = 0; right < n; right++) {
        if (s[right] != targetChar) {
            mismatches++;
        }
        
        // If more than 1 mismatch, shrink window
        while (mismatches > 1) {
            if (s[left] != targetChar) {
                mismatches--;
            }
            left++;
        }
        
        int len = right - left + 1;
        if (len > maxLen) maxLen = len;
    }
    
    return maxLen;
}

int solution(char* text) {
    int n = strlen(text);
    if (n == 0) return 0;
    
    // Find unique characters
    int uniqueChars[256] = {0};
    for (int i = 0; i < n; i++) {
        uniqueChars[(unsigned char)text[i]] = 1;
    }
    
    int maxResult = 0;
    for (int i = 0; i < 256; i++) {
        if (uniqueChars[i]) {
            char targetChar = (char)i;
            int curr = maxLengthForChar(text, targetChar);
            if (curr > maxResult) maxResult = curr;
        }
    }
    
    return maxResult;
}

int main() {
    char text[1001];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0; // Remove newline
    
    int result = solution(text);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26n)

For each of 26 possible characters, we scan the string once with sliding window

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for counters and variables

✓ Linear Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Character Frequency — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler