Terrible LeetCode in Kotlin: #3 Longest Substring Without Repeating Characters
Another day, another LeetCode question (for now). Today, I'm running through #3 on LeetCode, Longest Substring Without Repeating Characters. The input provides a string 's', with the output needing to be an integer that represents the longest substring that is possible from s without repeating any characters. My first impression of the problem was to use something similar to a sliding window, but with a little more nuance as to how I move about the string. I ultimately landed on a solution that adds the frequency of our characters into an array, and if we encounter an item that is already within our substring, we shrink our sliding window by one from the left as there is no way to encompass the new string without overlap. We then also slide over our window, until we no longer have the overlapping characters, indicated by our frequency. In the worst case, this solution seems like it would work in O(n) time, where n is the length of our string. My initial solution was slow compared to others, mainly because of the fact that I used a map instead of an array. When I switched over, the percentile was much more reasonable.
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/7 hours per week, [45/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Initial attempt, sliding window.