Longest Repeating Character Replacement - Practice Coding Problems

Longest Repeating Character Replacement - Problem

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Input & Output

Example 1 — Basic Case

$ Input: s = "ABAB", k = 2

› Output: 4

💡 Note: Replace the 2 'B's with 'A's (or 2 'A's with 'B's) to get "AAAA" or "BBBB". Maximum length is 4.

Example 2 — Limited Replacements

$ Input: s = "AABABBA", k = 1

› Output: 4

💡 Note: Replace one 'B' to get "AABAAAA" or similar. The longest substring of same characters is 4.

Example 3 — All Same Characters

$ Input: s = "AAAA", k = 2

› Output: 4

💡 Note: All characters are already the same, so no replacements needed. Length is 4.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only uppercase English letters
0 ≤ k ≤ s.length

Visualization

Tap to expand

Understanding the Visualization

Input

String "ABAB" with k=2 replacements allowed

Process

Find longest substring that can be made uniform

Output

Maximum length achievable is 4

Key Takeaway

🎯 Key Insight: Use sliding window - a window is valid when window_length - max_frequency ≤ k

Asked in

M Microsoft 45 a Amazon 38 G Google 32 f Facebook 28

The key insight is using a sliding window with character frequency tracking. A window is valid if window_length - max_frequency ≤ k. Best approach is sliding window with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window - Optimal Solution	O(n)	O(1)	Use sliding window with character frequency map to find longest valid substring efficiently
Brute Force - Check All Substrings	O(n³)	O(1)	Try every possible substring and count replacements needed for each

Sliding Window - Optimal Solution — Algorithm Steps

Initialize left and right pointers
Expand window by moving right pointer
Update character frequency map
Track maximum frequency in current window
Shrink window if replacements needed > k
Update maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Window

Start with left=0, right=0, track character frequencies

Expand Window

Move right pointer, update frequencies and max frequency

Contract if Needed

If replacements > k, move left pointer forward

Code -

solution.c — C

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

int solution(char* s, int k) {
    int n = strlen(s);
    if (n == 0) return 0;
    
    int left = 0;
    int maxLength = 0;
    int maxFreq = 0;
    int charCount[26] = {0}; // For uppercase A-Z
    
    for (int right = 0; right < n; right++) {
        // Add current character to window
        charCount[s[right] - 'A']++;
        
        // Update max frequency in current window
        if (charCount[s[right] - 'A'] > maxFreq) {
            maxFreq = charCount[s[right] - 'A'];
        }
        
        // Current window size
        int windowSize = right - left + 1;
        
        // If replacements needed > k, shrink window
        if (windowSize - maxFreq > k) {
            charCount[s[left] - 'A']--;
            left++;
        }
        
        // Update maximum length
        int currentLength = right - left + 1;
        if (currentLength > maxLength) {
            maxLength = currentLength;
        }
    }
    
    return maxLength;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string with two pointers, each element visited at most twice

✓ Linear Growth

Space Complexity

O(1)

Hash map stores at most 26 uppercase letters, constant space

✓ Linear Space

125.0K Views

High Frequency

~25 min Avg. Time

2.9K 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 - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler