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

Solution

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