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

Solution

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

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.HashSet;
4import java.util.List;
5import java.util.Scanner;
6
7class Solution {
8    public static List<String> substrings(String s, int k) {
9        HashSet<String> found = new HashSet<>();
10        ArrayList<String> res = new ArrayList<>();
11
12        // char -> index of (only) occurence in substring
13        HashMap<Character, Integer> occur = new HashMap<>();
14        // start index of substring
15        int start = 0;
16        // end index of substring
17        int end = 0;
18        while (end < s.length()) {
19            char ch = s.charAt(end);
20            // ensure s[start:end] has length <= k and distinct chars
21            int newStart = occur.getOrDefault(ch, end - k);
22            while (start <= newStart) {
23                occur.remove(s.charAt(start));
24                start++;
25            }
26
27            occur.put(ch, end);
28            end++;
29            if (end - start < k)
30                continue;
31            String sub = s.substring(start, end);
32            if (!found.contains(sub)) {
33                found.add(sub);
34                res.add(sub);
35            }
36        }
37
38        return res;
39    }
40
41    public static void main(String[] args) {
42        java.util.Scanner scanner = new java.util.Scanner(System.in);
43        String s = scanner.nextLine();
44        int k = Integer.parseInt(scanner.nextLine());
45        scanner.close();
46        List<String> res = substrings(s, k);
47        System.out.println(String.join(" ", res));
48    }
49}
50