algoadvance

Leetcode 424. Longest Repeating Character Replacement

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.

Clarifying Questions

1. Character Set: Is the input string s comprised only of uppercase English characters?
   • Assumption: Yes, the string s contains only uppercase English alphabet characters.
2. Constraints on k: Can k be larger or equal to the length of the string s?
   • Assumption: 0 <= k <= |s| where |s| is the length of the string.
3. Empty String: What should be the output if the input string is empty?
   • Assumption: If s is an empty string, the function should return 0.

Strategy

To solve this problem, we can use a sliding window approach to keep track of the substring that has the majority of its characters being the same.

1. Sliding Window Technique: We’ll use a window (left to right) to encompass the current substring.
2. Character Count: Maintain a count of characters within the window.
3. Majority Character: Track the count of the most frequent character in the current window.
4. Window Adjustment:
   • If the number of characters to be replaced (window length - count of majority character) exceeds k, then shrink the window from the left.
5. Result Tracking: Track the maximum length of valid windows throughout the process.

Code

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

int characterReplacement(const std::string& s, int k) {
    int left = 0;
    int maxCount = 0; // max count of a single character in the current window
    int maxLength = 0;
    std::unordered_map<char, int> charCount;

    for (int right = 0; right < s.size(); ++right) {
        charCount[s[right]]++;
        maxCount = std::max(maxCount, charCount[s[right]]);
        
        // If condition fails, we move the left pointer to make it valid
        while ((right - left + 1) - maxCount > k) {
            charCount[s[left]]--;
            left++;
        }
        
        maxLength = std::max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

int main() {
    std::string s = "AABABBA";
    int k = 1;
    
    int result = characterReplacement(s, k);
    std::cout << "The length of the longest substring after " << k << " replacements is: " << result << std::endl;
    
    return 0;
}

Time Complexity

• Time Complexity: O(N) where N is the length of the string s. Each character is processed at most twice, once when the right pointer enters the window and once when the left pointer leaves the window.
• Space Complexity: O(1). Although we use an unordered_map, the space complexity will be constant because there are only 26 uppercase English letters.

This approach ensures that we efficiently find the longest substring that can be formed by replacing at most k characters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?