Longest Repeating Character Replacement

The 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. Examples Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. 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 exist other ways to achieve this answer too. Constraints 1 <= s.length <= 105 s consists of only uppercase English letters. 0 <= k <= s.length Brute force solution func characterReplacement(_ s: String, _ k: Int) -> Int { let n = s.count let s = Array(s) var res = 0 for i in 0 ..< n { var count: [Character: Int] = [:] var maxF = 0 for j in i ..< n { count[s[j], default: 0] += 1 maxF = max(maxF, count[s[j]]!) let windowSize = (j - i + 1) let numOfCharsToReplace = (windowSize - maxF) let canReplace = (numOfCharsToReplace <= k) if canReplace { res = max(res, windowSize) } } } return res } Explanation First things first, we need to figure out which character we are going to replace. We can do this by using a dictionary. This way, we can calculate the most frequent character in the substring. After that, we will be able to calculate the number of characters to replace and check if we can replace the character. This algorithm is not very fast and takes O(n^2) time. We can improve it further and optimize it to achieve O(n) time complexity. ...