424. Longest Repeating Character Replacement

Longest Repeating Character Replacement (LeetCode 424) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.

• Blind 75 · #14 of 75 · Sliding Window
• NeetCode 150 · #17 of 150 · Sliding Window
• NeetCode 250 · #39 of 250 · Sliding Window

How to solve Longest Repeating Character Replacement

Longest Repeating Character Replacement is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Work towards the solution in these steps:

1. Try using a sliding window approach to efficiently examine substrings rather than checking all possible substrings explicitly.
2. Since characters can be replaced up to k times, consider how to maintain a window where at most k characters differ from the most frequent character in that window.
3. Keep track of the count of each character within the current window to help determine if the window is valid based on the allowed replacements.

The reference solution runs in O(n) time and O(1) space.

The Longest Repeating Character Replacement solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Hash Table, String, Sliding Window.

Reported in interviews at Google, Amazon, Wish.

How to practise Longest Repeating Character Replacement on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Longest Repeating Character Replacement in the code editor, or read the Longest Repeating Character Replacement editorial for a worked solution with its approach and complexity analysis.

Where Longest Repeating Character Replacement sits in the DSA pattern sheet

• Sliding Window pattern guide
• Variable Size (Condition-Based) subpattern
• The full DSA patterns sheet

Problems related to Longest Repeating Character Replacement

Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:

• Contains Duplicate II — Easy, same subpattern
• Continuous Subarrays — Medium, same subpattern
• Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
• Frequency of the Most Frequent Element — Medium, same subpattern
• Fruit Into Baskets — Medium, same subpattern
• Jump Game VII — Medium, same subpattern

Longest Repeating Character Replacement FAQ