Key Insights — Use a sliding window with a hashmap to track the counts of the characters. The window is valid if the window length minus the most frequent character is less than or equal to the number of allowed replacements.
One of my first thoughts on this is to create a hashmap of each character to the positions it occupies. Then somehow analyze the list of positions to find the ones that have the minimum distance. Perhaps subtracting the character indexes could reveal which characters are the closest together.
Step 1
This function constructs the spacing between characters in a string. For example, if s="aabbcba" then the spacing for “a” is [0,0,4,0]. It includes the beginning and end of the string. This sets us to to determine which character can create the longest repeating sequence through substitution.
The next step is to create a function that will take these “diff” arrays and calculate the longest possible repeating substring from them.
Step 2?
This is meant to be the function that calculates the maximum length substring for a “diff” array described above. It essentially looks at the array and tries to find the longest subarray where the sum is <= k. It uses the two pointer method to make the ahead pointer move ahead if the sum current_k <= k and the behind pointer move head if current_k > k. This is meant to keep the current sum hovering around k.
The problem with this approach is that mixing the diff values with characters makes the substring length hard to calculate. For example, for the string “babbab” the diff array for “a” is [1,2,1]. For k=2 it is clear that the maximum substring length for “a” is 4. This is created by replacing the two “b”s in the middle. However, coming up with that sum based on the ahead and behind pointer both pointing at 2 is challenging.
A simpler representation for the arrays is to just have 0sand 1s represent whether the character is present. So for the string “babbab” the array for “a” would look like [0,1,0,0,1,0]. The per-character arrays are the same length as the original string. I’m going to start again with this approach.
Initial Solution
This passes all of the test cases. However, it only beat 5% of submissions on runtime and 10% on memory usage. I’m going to check the NeetCode video to see if there’s a cleaner solution.
Improved Solution
The optimal solution has some improvements on the solution that I came up with. The main one is that instead of having a hashmap of lists of character positions, the solution just has a hashmap of the counts of each character. It uses the hashmap to maintain a valid sliding window. The valid condition is that ahead — behind — max_freq + 1 <= k. This ensures that there are enough replacement characters to fill in the k non-most-frequent characters.
This one also passes all of the test cases. It only beats 10% of submissions on runtime, but it now beats 77% of submissions on memory usage.
Wrap Up
I’m proud of myself for sticking with it and coming up with a solution on my own that passed all of the test cases. There was some room to improve the solution, but it’s still a good feeling to solve a LeetCode problem without help.
