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
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.