# 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

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;
};

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;
}
}
?>

This site uses Akismet to reduce spam. Learn how your comment data is processed.