Longest Repeating Character Replacement

MEDIUM

Description

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.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:

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

Approaches

Checkout 2 different approaches to solve Longest Repeating Character Replacement. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Optimization

This approach iterates through all possible substrings of the input string s. For each substring, it calculates the minimum number of replacements required to make all characters in it the same. If this number is within the allowed limit k, the length of the substring is considered as a potential answer. The maximum length found among all valid substrings is the result.

Algorithm

Initialize maxLength = 0.
Iterate through the string with a starting pointer i from 0 to n-1.
For each i, start an inner loop with an ending pointer j from i to n-1.
Maintain a frequency map (e.g., an array of size 26) for the characters in the substring s[i..j].
In the inner loop, as j increments, update the frequency of s[j].
Find the frequency of the most common character in the current substring s[i..j], let's call it maxFreq.
The number of replacements needed is (j - i + 1) - maxFreq.
If (j - i + 1) - maxFreq <= k, then this substring is a candidate. Update maxLength = max(maxLength, j - i + 1).
After both loops complete, maxLength will hold the answer.

The naive brute-force approach would be to check every substring and for each substring, check against all 26 possible characters, leading to an O(n^3) complexity. We can optimize this.

A better brute-force method involves iterating through all possible start and end points of a substring, which is O(n^2). For each substring, we can determine the number of replacements needed more efficiently.

The number of replacements for a substring is its length minus the frequency of its most common character. To find this, we can maintain a frequency map for the characters within the current substring.

As we extend the substring by one character (by moving the end pointer), we update the frequency map and find the new most frequent character. This check takes constant time (O(1) since there are only 26 uppercase letters).

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            int[] charCounts = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                charCounts[s.charAt(j) - 'A']++;
                maxFreq = Math.max(maxFreq, charCounts[s.charAt(j) - 'A']);
                int replacementsNeeded = (j - i + 1) - maxFreq;
                if (replacementsNeeded <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times. Inside the inner loop, operations are constant time.Space Complexity: O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant.

Pros and Cons

Pros:

Simple to understand and implement.
It's a direct translation of the problem statement.

Cons:

Inefficient for large inputs. It will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 10^5).

Code Solutions

Checking out 3 solutions in different languages for Longest Repeating Character Replacement. Click on different languages to view the code.

class Solution { public int characterReplacement ( String s , int k ) { int [] counter = new int [ 26 ]; int i = 0 ; int j = 0 ; for ( int maxCnt = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); ++ counter [ c - 'A' ]; maxCnt = Math . max ( maxCnt , counter [ c - 'A' ]); if ( i - j + 1 - maxCnt > k ) { -- counter [ s . charAt ( j ) - 'A' ]; ++ j ; } } return i - j ; } }

Video Solution

Watch the video walkthrough for Longest Repeating Character Replacement

Patterns:

Sliding Window

Data Structures:

Hash TableString

Companies:

ByteDance |Flipkart |Yandex |Turing |