Longest Repeating Character Replacement

                                            
class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.length();
        int maxFreq = 0, maxLength = 0;
        vector<int> count(26, 0);
        int start = 0;
        
        for (int end = 0; end < n; end++) {
            maxFreq = max(maxFreq, ++count[s[end] - 'A']);
            while (end - start + 1 - maxFreq > k) {
                count[s[start] - 'A']--;
                start++;
            }
            maxLength = max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
};

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

                                            
class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if not s:
            return 0
        
        max_length = 0
        max_count = 0
        start = 0
        count_map = {}
        
        for end in range(len(s)):
            count_map[s[end]] = count_map.get(s[end], 0) + 1
            max_count = max(max_count, count_map[s[end]])
            
            if end - start + 1 - max_count > k:
                count_map[s[start]] -= 1
                start += 1
                
            max_length = max(max_length, end - start + 1)
        
        return max_length

                                            
int characterReplacement(char* s, int k) {
    int maxLen = 0;
    int maxCount = 0;
    int charCount[26] = {0};
    int start = 0;
    
    for (int end = 0; s[end] != '\0'; end++) {
        charCount[s[end] - 'A']++;
        maxCount = fmax(maxCount, charCount[s[end] - 'A']);
        
        if (end - start + 1 - maxCount > k) {
            charCount[s[start] - 'A']--;
            start++;
        }
        
        maxLen = fmax(maxLen, end - start + 1);
    }
    
    return maxLen;
}

                                            
public class Solution {
    public int CharacterReplacement(string s, int k) 
    {
        int[] count = new int[26];
        int maxCount = 0;
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.Length; end++) {
            maxCount = Math.Max(maxCount, ++count[s[end] - 'A']);
            
            if (end - start + 1 - maxCount > k) {
                count[s[start] - 'A']--;
                start++;
            }
            
            maxLength = Math.Max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

                                            
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    let maxCount = 0, maxLength = 0;
    let charCount = new Array(26).fill(0);
    let start = 0;
    
    for (let end = 0; end < s.length; end++) {
        maxCount = Math.max(maxCount, ++charCount[s.charCodeAt(end) - 65]);
        
        if (end - start + 1 - maxCount > k) {
            charCount[s.charCodeAt(start) - 65]--;
            start++;
        }
        
        maxLength = Math.max(maxLength, end - start + 1);
    }
    
    return maxLength;
};

                                            
function characterReplacement(s: string, k: number): number {
    let maxCount = 0;
    let maxLength = 0;
    let start = 0;
    const charCount = new Array(26).fill(0);

    for (let end = 0; end < s.length; end++) {
        const charIndex = s.charCodeAt(end) - 'A'.charCodeAt(0);
        charCount[charIndex]++;

        maxCount = Math.max(maxCount, charCount[charIndex]);

        if (end - start + 1 - maxCount > k) {
            const startCharIndex = s.charCodeAt(start) - 'A'.charCodeAt(0);
            charCount[startCharIndex]--;
            start++;
        }

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

    return maxLength;
};

                                            
class Solution {
    /**
     * @param String $s
     * @param Integer $k
     * @return Integer
     */
    function characterReplacement($s, $k) {
        $max = 0;
        $start = 0;
        $charCount = [];
        $maxCharCount = 0;
        
        for ($end = 0; $end < strlen($s); $end++) {
            $charCount[$s[$end]] = ($charCount[$s[$end]] ?? 0) + 1;
            $maxCharCount = max($maxCharCount, $charCount[$s[$end]]);
            
            if ($end - $start + 1 - $maxCharCount > $k) {
                $charCount[$s[$start]]--;
                $start++;
            }
            
            $max = max($max, $end - $start + 1);
        }
        
        return $max;
    }
}

                                            
class Solution {
    /**
     * @param String $s
     * @param Integer $k
     * @return Integer
     */
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var maxCount = 0
        var maxLength = 0
        var charCount = [Character: Int]()
        var start = 0
        
        for end in 0..<s.count {
            let char = Array(s)[end]
            charCount[char, default: 0] += 1
            maxCount = max(maxCount, charCount[char]!)
            
            if end - start + 1 - maxCount > k {
                let startChar = Array(s)[start]
                charCount[startChar]! -= 1
                start += 1
            }
            
            maxLength = max(maxLength, end - start + 1)
        }
        
        return maxLength
    }
}

                                            
class Solution {
    fun characterReplacement(s: String, k: Int): Int {
        var result = 0
        var maxCount = 0
        var start = 0
        val count = IntArray(26)
        
        for (end in s.indices) {
            maxCount = maxOf(maxCount, ++count[s[end] - 'A'])
            
            if (end - start + 1 - maxCount > k) {
                count[s[start] - 'A']--
                start++
            }
            
            result = maxOf(result, end - start + 1)
        }
        
        return result
    }
}

                                            
func characterReplacement(s string, k int) int {
    maxLen := 0
    for i := 0; i < 26; i++ {
        left, right, count := 0, 0, 0
        freq := make([]int, 26)
        for right < len(s) {
            freq[s[right]-'A']++
            count = max(count, freq[s[right]-'A'])
            for right-left+1-count > k {
                freq[s[left]-'A']--
                left++
            }
            maxLen = max(maxLen, right-left+1)
            right++
        }
    }
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {String} s
# @param {Integer} k
# @return {Integer}
def character_replacement(s, k)
    # Start your code here
    max_length = 0
    max_count = 0
    counts = Hash.new(0)
    start_idx = 0
    
    s.each_char.with_index do |char, end_idx|
        counts[char] += 1
        max_count = [max_count, counts[char]].max
        
        if (end_idx - start_idx + 1) - max_count > k
            counts[s[start_idx]] -= 1
            start_idx += 1
        end
        
        max_length = [max_length, end_idx - start_idx + 1].max
    end
    
    max_length
end

                                            
object Solution {
    def characterReplacement(s: String, k: Int): Int = {
        val n = s.length
        var left = 0
        var maxCount = 0
        var maxLength = 0
        var frequency = Array.ofDim[Int](26)
        
        for (right <- 0 until n) {
            val index = s(right) - 'A'
            frequency(index) += 1
            maxCount = math.max(maxCount, frequency(index))
            
            if (right - left + 1 - maxCount > k) {
                frequency(s(left) - 'A') -= 1
                left += 1
            }
            
            maxLength = math.max(maxLength, right - left + 1)
        }
        
        maxLength
    }
}

                                            
impl Solution {
    pub fn character_replacement(s: String, k: i32) -> i32 {
        let mut max_length = 0;
        let s = s.as_bytes();
        for c in b'A'..=b'Z' {
            let mut start = 0;
            let mut end = 0;
            let mut count = 0;
            while end < s.len() {
                if s[end] != c {
                    count += 1;
                }
                while count > k {
                    if s[start] != c {
                        count -= 1;
                    }
                    start += 1;
                }
                max_length = max_length.max(end - start + 1);
                end += 1;
            }
        }
        max_length as i32
    }
}

To solve this coding challenge, we'll need to implement a strategy that maintains the length of the longest substring with repeating characters after allowing at most

k

changes in the characters.

Explanation

The problem can be elegantly solved using a sliding window technique. This approach helps manage a dynamic window that can 'slide' over the string, expanding and contracting as needed to find the maximum length of the desired substring. Here's a step-by-step approach to understand how the solution works:

Understanding the Sliding Window :

We initialize a window that starts at the beginning of the string.
We will expand the window by including characters from the right.
If the condition that the number of characters to be replaced exceeds
k

is met, we will shrink the window from the left.

Character Count Management :

We need to keep track of the frequency of characters within the current window. This can be managed using a dictionary or a list that tracks occurrences of each character.

Max Frequency Character :

Within the current window, keep track of the count of the most frequent character.
This helps in determining if the current window length minus the max frequency character is within the allowable replacements (
k

).

Adjusting the Window :

If the window length (right - left + 1) minus the count of the most frequent character is greater than
k

, it signifies we have more than
k

characters that need replacement. Hence, we should contract the window from the left until the condition is satisfied again.

Recording the Maximum Length :

Keep track of the maximum length of such a window during this entire process.

Pseudocode

                                            
// Initialize variables
max_length = 0 // To store the length of the longest valid substring found
max_frequency = 0 // To store the count of the most frequently occurring character in the current window
left_pointer = 0 // Start of the current window
char_count = {} // Dictionary to store the frequency of each character in the current window

// Loop through each character in the string using right_pointer
for right_pointer from 0 to len(s) - 1:
// Include character at right_pointer in the window, increment its count
char_count[s[right_pointer]] = char_count.get(s[right_pointer], 0) + 1

// Update max_frequency with the frequency of the most common character in current window
max_frequency = max(max_frequency, char_count[s[right_pointer]])

// Check if current window size minus maximum character frequency is greater than k
if (right_pointer - left_pointer + 1 - max_frequency) > k:
// If condition is true, shrink window from the left
char_count[s[left_pointer]] -= 1
left_pointer += 1

// Calculate and update max_length
max_length = max(max_length, right_pointer - left_pointer + 1)

return max_length

Step-by-Step Explanation

Initialization :

max_length

is set to 0 as initially, we haven't found any valid window.
max_frequency

is also 0 initially because the window is empty.
left_pointer

(start of the window) is set to the start of the string.
char_count

is an empty dictionary that will hold the count of characters within the current window.

Sliding the Window :

Loop through the string using a
right_pointer

which marks the end of the current window.
For each character
s[right_pointer]

, increase its count in
char_count

.
Update
max_frequency

to be the highest frequency of any character in the current window.

Window Adjustment :

If the number of characters to replace within the current window exceeds
k

, then start shrinking the window from the left by moving
left_pointer

rightward.
Decrement the count of the character at
left_pointer

in
char_count

.

Recording Maximum Length :

Each time the window is adjusted, calculate and update
max_length

if the current window is larger than the previously recorded maximum.

This process continues until the entire string has been processed and ensures that the solution is optimal and efficient in terms of time complexity.