424 — Longest Repeating Character Replacement
Restating Info We’re Already Given:
- Given a string s of length between 1 and 100,000 inclusive with all uppercase English letters, we want to find the longest substring of 1 character with k wildcards (a character that is any character but the most frequent one in the substring).
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- N/A
Discuss Naive Solution:
Naively, we could check every possible substring and see which one is the longest substring meeting the requirements. There are n² possible substrings and each substring takes O(n) time to determine whether it fits the requirements, for a time complexity of O(n³).
Discuss Optimal Solution:
Optimally, we can do this in linear time. To do so, we must keep track of:
- the frequency of the most frequent character seen in the current substring, maxFreqMostCommonChar
- the length of longest substring we can generate within the problem’s constraints, longestLengthSubstring
- using a dictionary, the frequency of every character in the current substring, charCounter (Note: I use a collections.defaultdict(int) to avoid having to check for a key’s existence for each step)
Going left to right for each of the characters, we first increase the frequency current character as we’ve seen it 1 more time. Then, we update maxFreqMostCommonChar, which is either its current frequency (if different from the current character) or the new frequency of the current character. Then, we check if we have a new longestLengthSubstring. If we do, then we increment it by 1. Otherwise, we get decrement the occurrence of the least recent character (smallest index character in the current substring) as it no longer fits within our constraints.
Code Optimal Solution:
Runtime/Space Complexity:
The optimal solution runs in linear time with a linear space complexity in the worst case, where the longestLengthSubstring is the length of the passed in string s, implying that the charCounter is has 1 entry for each char in s.
Test Cases:
- String length 1
- k = 0
- k = length string
- String all same character
- String all unique characters
