Position: E4
YOE: 4
Hi all,
Interviewer joined a few mins late and there were some technical difficulties before getting started but afterwards I was asked a question https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters but we needed to return the actual substring.
Asked clarifying question about the following input / edge cases:
Empty/Null input, k <= 0, are the characters UTF-8 or other, will there be any non alphabetic characters in input, what about capital versions, should we count uppercase same as lowercase or not
Then discussed Space/Time of O(n) / O(k) where n = len(s)
Solution
Very similar to provided solution from LeetCode with one difference being instead of using max() to update the longest substring, placing it in an if() and maintaining a pointer to the longest substr start index alongside longestSubstr length.
def longest_substring_with_k_distinct_characters(s: str, k: int) -> str:
longest_substr = 0
char_freq = {}
start = 0
substr_start = 0
for i in range(len(s)):
char = s[i]
if char not in char_freq:
char_freq[char] = 0
char_freq[char] += 1
while len(freq) > k:
char_freq[s[start]] -= 1
if char_freq[s[start]] == 0:
del char_freq[s[start]]
start += 1
if longest_substr <= i - start + 1:
longest_substr = i - start + 1
substr_start = start
return s[substr_start:substr_start + longest_substr]