Substrings of size K with K distinct chars

Problems
1

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:
            found.add(sub)
            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)) {
                found.add(sub);
                res.add(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/