Scale Engineer

Longest Repeating Character Replacement

Med
#0411Time: 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: O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant.10 companies
Patterns
Sliding Window
Data structures
Hash TableString
Companies
ByteDanceFlipkartYandexTuring

Prompt

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 <= 105
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem