Solution For Longest Repeating Character Replacement

The Longest Repeating Character Replacement problem on leetcode asks us to find the longest substring in a given string s, where we can replace at most k characters in the substring such that all the characters in the substring are the same.

To find the solution, we can use a sliding window approach where we maintain a window of characters and keep track of the maximum repeating character within the window. If the number of non-repeating characters within the window exceeds k, we decrement the size of the window by moving the left pointer, otherwise, we increment the size of the window by moving the right pointer.

Algorithm:

1. Initialize a hashmap to keep track of the frequency of each character in the given string.
2. Define pointers, left and right, to denote the limits of the window.
3. Define a variable, max_char_count, to keep track of the maximum repeating count of any character within the window.
4. Define a variable, max_length, to keep track of the maximum length of a substring that can be formed within the window.
5. Move the right pointer forward until the window has at most k non-repeating characters.
6. Update the max_length if the current window has a longer substring than previous windows.
7. Move the left pointer forward and decrement the frequency of the left character in the hashmap.
8. If the left character had the maximum repeating count, recalculate the max_char_count.
9. Repeat steps 5-8 until the right pointer goes beyond the end of the string.
10. Return max_length as the final result.

Here is the Python code:

“`python
def characterReplacement(s: str, k: int) -> int:
freq_map = {}
left = right = max_char_count = max_len = 0

while right < len(s):
    freq_map[s[right]] = freq_map.get(s[right], 0) + 1
    max_char_count = max(max_char_count, freq_map[s[right]])

    if (right-left+1) - max_char_count > k:
        freq_map[s[left]] -= 1
        left += 1

    max_len = max(max_len, right-left+1)
    right += 1

return max_len

“`

The time complexity of the above algorithm is O(n) and the space complexity is O(1) since the size of the hashmap is at most 26 (for all possible lowercase English alphabets).

Step by Step Implementation For Longest Repeating Character Replacement

class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length();
        int[] count = new int[26];
        int start = 0, maxCount = 0, maxLength = 0;
        for (int end = 0; end < len; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # We will use a sliding window approach to solve this problem.
        # We will keep track of the most frequent character in the current window.
        # If the most frequent character occurs more than k times, we can replace it with any other character
        # and the window will still be a valid solution.
        # Therefore, we just need to find the longest window where the most frequent character occurs less than k times.
        
        # We will use a hashmap to keep track of the frequencies of each character.
        # We will also keep track of the left and right indices of the current window.
        # We will also keep track of the maximum length window so far.
        
        max_len = 0
        left = 0
        right = 0
        char_freq = {}
        
        # Loop through the string
        while right < len(s):
            # Add the character at the right index to the hashmap
            char_freq[s[right]] = char_freq.get(s[right], 0) + 1
            
            # Update the max length window if necessary
            max_len = max(max_len, right - left + 1)
            
            # If the most frequent character occurs more than k times,
            # we can replace it with any other character and the window will still be valid.
            # Therefore, we will shrink the window from the left until the most frequent character
            # occurs less than k times.
            while char_freq[s[right]] - 1 >= k:
                # Remove the character at the left index from the hashmap
                char_freq[s[left]] -= 1
                
                # Update the left index
                left += 1
            
            # Update the right index
            right += 1
        
        # Return the maximum length window
        return max_len

var characterReplacement = function(s, k) {
    let len = s.length;
    let count = [];
    let max = 0;
    let start = 0;
    
    for(let i = 0; i < 26; i++)
        count.push(0);
    
    for(let end = 0; end < len; end++){
        count[s.charCodeAt(end) - 'A'.charCodeAt(0)]++;
        max = Math.max(max, count[s.charCodeAt(end) - 'A'.charCodeAt(0)]);
        
        if(end - start + 1 - max > k){
            count[s.charCodeAt(start) - 'A'.charCodeAt(0)]--;
            start++;
        }
    }
    return len - start;
};

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        int res = 0;
        for(char c = 'A'; c <= 'Z'; c++) {
            int i = 0, j = 0, count = 0, maxCount = 0;
            while(j < n) {
                if(s[j] == c) {
                    count++;
                } else {
                    maxCount = max(maxCount, count);
                    count = 0;
                    i = j+1;
                }
                j++;
            }
            maxCount = max(maxCount, count);
            res = max(res, maxCount + k);
        }
        return res;
    }
};

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            string s = "ABAB"; 
            int k = 2; 

            Console.WriteLine(CharacterReplacement(s, k)); 
            Console.ReadLine(); 
        } 

        public static int CharacterReplacement(string s, int k) 
        { 
            if (string.IsNullOrEmpty(s)) 
            { 
                return 0; 
            } 

            int maxCount = 0; 
            int start = 0; 
            int maxLength = 0; 
            Dictionary map = new Dictionary(); 

            for (int end = 0; end < s.Length; end++) 
            { 
                char c = s[end]; 
                if (!map.ContainsKey(c)) 
                { 
                    map.Add(c, 0); 
                } 
                map[c]++; 
                maxCount = Math.Max(maxCount, map[c]); 

                while (end - start + 1 - maxCount > k) 
                { 
                    char sc = s[start]; 
                    map[sc]--; 
                    start++; 
                } 

                maxLength = Math.Max(maxLength, end - start + 1); 
            } 

            return maxLength; 
        } 
    } 
}