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

Categories: Leetcode