Amazon Online Assessment (OA) - Substrings of Size K with K-1 Distinct Characters

Find all unique substrings containing distinct characters of length k given a string s containing only lowercase alphabet characters.

Examples

Example 1:

Input: s = xabxcd, k = 4
Output: ["abxc", "bxcd"]
Explanation:

The substrings are xabx, abxc, and bxcd. However x repeats in the xabx, so it is not a valid substring of a distinct characters.

Example 2:

Input: s = aabcdbcd, k = 3
Output: ["abc", "bcd", "cdb", "dbc"]
Explanation:

The substrings with distinct characters are abc, bcd, cdb, dbc, and again bcd. However, we are looking for unique substrings, so we discard the last one which repeats.

Constraints:

k is a positive number less than or equal to 26.

Try it yourself

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))