Formatted question description:

1100. Find K-Length Substrings With No Repeated Characters




Given a string S, return the number of substrings of length K with no repeated characters.

Example 1:

Input: S = “havefunonleetcode”, K = 5

Output: 6


There are 6 substrings they are:


Example 2:

Input: S = “home”, K = 5

Output: 0


Notice K can be larger than the length of S. In this case is not possible to find any substring.


  1. 1 <= S.length <= 10^4
  2. All characters of S are lowercase English letters.
  3. 1 <= K <= 10^4


If S has length less than K, then it is not possible to find any substring, so return 0.

Use a map to store each character and its number of occurrences in each substring. Initially, add the first K characters of S to the map together with their numbers of occurrences. Each time a new substring is met, decrease the number of occurrences of the first character in the previous substring by 1 and increase the number of occurrences of the last character in the current substring by 1. If a character’s number of occurrences becomes 0, remove the character from the map. For each substring (including the first substring), the substring doesn’t contain repeated characters if and only if the map contains exactly K keys. In this way, the number of substrings of length K with no repeated characters can be calculated.

class Solution {
    public int numKLenSubstrNoRepeats(String S, int K) {
        if (S == null || S.length() < K)
            return 0;
        int length = S.length();
        Map<Character, Integer> letterCountMap = new HashMap<Character, Integer>();
        for (int i = 0; i < K; i++) {
            char c = S.charAt(i);
            int count = letterCountMap.getOrDefault(c, 0);
            letterCountMap.put(c, count);
        int substringsCount = 0;
        if (letterCountMap.keySet().size() == K)
        for (int i = K; i < length; i++) {
            char prevC = S.charAt(i - K);
            char curC = S.charAt(i);
            int prevCount = letterCountMap.getOrDefault(prevC, 0);
            if (prevCount == 0)
                letterCountMap.put(prevC, prevCount);
            int curCount = letterCountMap.getOrDefault(curC, 0);
            letterCountMap.put(curC, curCount);
            if (letterCountMap.keySet().size() == K)
        return substringsCount;

All Problems

All Solutions