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

Explanation:

There are 6 substrings they are : 'havef','avefu','vefun','efuno','etcod','tcode'.

Example 2:

Input:

S = "home", K = 5

Output:

0

Explanation:

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

 

Note:

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

 

Quite straight forward solution.

the brute force way is foreach K chars, check dupes.

to optimize that, push next char and remove last instead, so same work won’t be done multiple times

<?php
class Solution {

    /**
     * @param String $S
     * @param Integer $K
     * @return Integer
     */
    function numKLenSubstrNoRepeats($S, $K) {
        if($K > strlen($S)){
            return 0;
        }
        // This is not necessary in PHP
        $arr = str_split($S);
        $dic = [];
        $result = 0;
        
        // Helper, any repeated chars so far?
        $unique = static function() use (&$dic) {
            foreach($dic as $v){
                if ($v > 1){
                    return false;
                }
            }
            return true;
        };

        // Load first K chars
        for($i = 0; $i < $K; $i ++){
            if(isset($dic[$arr[$i]])){
                $dic[$arr[$i]]++;
            } else {
                $dic[$arr[$i]] = 1;
            }
            
        }
        // First K has repeat? update counter
        if($unique()){
             $result++;
        }

        // Starting from K, take next char and remove the last one, update dictionary, and check after each round
        for($in = $K; $in < strlen($S); $in ++){
            if(isset($dic[$arr[$in]])){
                $dic[$arr[$in]]++;
            } else {
                $dic[$arr[$in]] = 1;
            }
            
            $out = $in-$K;
            $dic[$arr[$out]]--;
            
            if($unique()){
                $result++;
            }
        }
            
        return $result;
    }
}
?>