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

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        Scanner scanner = new 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