Terrible LeetCode in Kotlin:
Another day, another LeetCode question (for now). Today, I'm running through #424 Longest Repeating Character Replacement. The problem provides a string s and an integer k, with the expected output being the length of the longest subarray of repeating characters that is possible, with or without replacing k characters.
Given that the problem's input size was limited to 10^5, I suspected that the approach would be somewhere around O(n) runtime, where n is the length of the string. The brute force solution would be to check every subarray in O(n^2) time, but we can use a sliding window to improve our times.
My approach uses a frequencyMap, along with a reference to the "dominant character". Any copy of the dominant character, does not count against k, while any other character does. If a character manages to achieve the same frequency as the dominant character (or more), then we set that to the dominant character. We continue growing the substring until we can no longer grow any more by taking on new characters. After that, we shrink the substring by 1 from the left hand side, which will either allow us to continue to grow in the next iteration, or will not and cause us to shrink until we are able to.
This approach should run in O(n) time, as we only really iterate over the string a constant multiple of n times.
I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.
Current Grind:
Grind75 list, 22 weeks/16 hours per week, [104/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion
09:49 - Coding Begins (Sliding Window)