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

## Solution

``````from typing import List
def substrings(s: str, k: int) -> List[str]:
found = set()
res = []
# char -> index of (only) occurence in substring
occur = {}
# start index of substring
start = 0
# end index of substring
end = 0
while end < len(s):
ch = s[end]
# ensure s[start:end] has length <= k and distinct chars
new_start = occur.get(ch, end - k)
while start <= new_start:
occur.pop(s[start])
start += 1
occur[ch] = end
end += 1
if end - start < k:
continue
sub = s[start:end]
if sub not in found:
res.append(sub)
return res
if __name__ == '__main__':
s = input()
k = int(input())
res = substrings(s, k)
print(' '.join(res))
``````
``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
class Solution {
public static List<String> substrings(String s, int k) {
HashSet<String> found = new HashSet<>();
ArrayList<String> res = new ArrayList<>();
// char -> index of (only) occurence in substring
HashMap<Character, Integer> occur = new HashMap<>();
// start index of substring
int start = 0;
// end index of substring
int end = 0;
while (end < s.length()) {
char ch = s.charAt(end);
// ensure s[start:end] has length <= k and distinct chars
int newStart = occur.getOrDefault(ch, end - k);
while (start <= newStart) {
occur.remove(s.charAt(start));
start++;
}
occur.put(ch, end);
end++;
if (end - start < k)
continue;
String sub = s.substring(start, end);
if (!found.contains(sub)) {
}
}
return res;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int k = Integer.parseInt(scanner.nextLine());
scanner.close();
List<String> res = substrings(s, k);
System.out.println(String.join(" ", res));
}
}
``````

This is a companion discussion topic for the original entry at https://algo.monster/problems/substrings_of_size_K_with_K_distinct_chars/