MEDIUM NC#17 Blind #51 Sliding Window

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

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •String/array indexing
  • •Set/Map frequency counting
  • •Pointer movement invariants

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Sliding Window reasoning pattern
  • •Apply Backtracking reasoning pattern

💡 Approach

  • → Use sliding window to maintain current substring
  • → Track max frequency of any character in window
  • → Valid window: (window size - max frequency) <= k
  • → If invalid, shrink from left
  • → Expand to right and track max length
  • → Time: O(n), Space: O(26) constant

🧭 Prerequisites

#3 Longest Substring Without Repeating Characters #209 Minimum Size Subarray Sum

🛠️ Hints & Pitfalls

Hints

  • •Use sliding window to maintain current substring
  • •Track max frequency of any character in window
  • •Valid window: (window size - max frequency) <= k

Common Pitfalls

  • •If invalid, shrink from left
  • •Expand to right and track max length
  • •Time: O(n), Space: O(26) constant

🧪 Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
characterReplacement('ABAB', 2);
Expected:
4
Test Case 2
Not run
Input:
characterReplacement('AABABBA', 1);
Expected:
4
Test Case 3
Not run
Input:
characterReplacement('AAAA', 2);
Expected:
4

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#3 Longest Substring Without Repeating Characters #76 Minimum Window Substring #121 Best Time to Buy and Sell Stock #209 Minimum Size Subarray Sum #485 Max Consecutive Ones
⌘K Search ⌘↩ Run ⌘S Submit