Amazon Online Assessment (OA) 2021 - Substrings of Size K with Distinct Characters | HackerRank SHL

Solution

1from typing import List
2
3def substrings(s: str, k: int) -> List[str]:
4    found = set()
5    res = []
6
7    # char -> index of (only) occurence in substring
8    occur = {}
9    # start index of substring
10    start = 0
11    # end index of substring
12    end = 0
13    while end < len(s):
14        ch = s[end]
15        # ensure s[start:end] has length <= k and distinct chars
16        new_start = occur.get(ch, end - k)
17        while start <= new_start:
18            occur.pop(s[start])
19            start += 1
20
21        occur[ch] = end
22        end += 1
23        if end - start < k:
24            continue
25        sub = s[start:end]
26        if sub not in found:
27            found.add(sub)
28            res.append(sub)
29
30    return res
31
32if __name__ == '__main__':
33    s = input()
34    k = int(input())
35    res = substrings(s, k)
36    print(' '.join(res))
37