# K-Substring with K different characters

`String`

### Description

Given a string S and an integer K.\
Calculate the number of substrings of length K and containing K different characters

### Example

```
String: "abcabc"
K: 3

Answer: 3
substrings:  ["abc", "bca", "cab"]
```

```
String: "abacab"
K: 3

Answer: 2
substrings: ["bac", "cab"]
```

## Solution & Analysis

双指针，`O(n)`时间法度。

`i`从0开始loop，`j`也从0开始，但每一个新`i`的循环，`j`不返回，继续往前。

用一个HashMap/HashSet来保存当前substring里的字母，找到长度为k且不包含重复字母的substring后，remove `i`所指的字母，`i++`，继续寻找。

#### Sliding Window - Two Pointer

```java
public class Solution {
    /**
     * @param stringIn: The original string.
     * @param K: The length of substrings.
     * @return: return the count of substring of length K and exactly K distinct characters.
     */
    public int KSubstring(String stringIn, int K) {
        if (stringIn == null || stringIn.length() == 0 || K <= 0) {
            return 0;
        }
        int count = 0;
        HashMap<Character, Integer> charMap = new HashMap<>();
        HashSet<String> resultSet = new HashSet<String>();
        int len = stringIn.length();
        int j = 0;
        for (int i = 0; i < len; i++) {
            while (j < len && charMap.size() < K) {`
                char c = stringIn.charAt(j);
                if (charMap.containsKey(c)) {
                    break;
                }
                charMap.put(c, 1);
                j++;
                if (charMap.size() == K) {
                    resultSet.add(stringIn.substring(i, j));
                }
            }
            charMap.remove(stringIn.charAt(i));
        }
        return resultSet.size();
    }
}
```

#### Sliding Window - Two Pointer

Two pointer O(N)\
create two hashSet, One set to store Character, One Set to store the substring

i start index, test every start index, to check whether it can be a substring of length K and containing different characters\
if contains duplicate character , break, start from next index

```java
public class Solution {
    /**
     * @param stringIn: The original string.
     * @param K: The length of substrings.
     * @return: return the count of substring of length K and exactly K distinct characters.
     */
    public int KSubstring(String stringIn, int K) {
        if (stringIn == null || stringIn.length() == 0 || K <= 0) {
            return 0;
        }
        int count = 0;
        HashSet<Character> charSet = new HashSet<>();
        HashSet<String> resultSet = new HashSet<String>();
        int len = stringIn.length();
        int j = 0;
        for (int i = 0; i <= len - K; i++) {
            while (j < len && charSet.size() < K) {
                char c = stringIn.charAt(j);
                if (!charSet.contains(c)) {
                    charSet.add(c);
                } else {
                    break;
                }
                j++;
                if (charSet.size() == K) {
                    resultSet.add(stringIn.substring(i, j));
                }
            }
            charSet.remove(stringIn.charAt(i));
        }
        return resultSet.size();
    }
}
```

## Reference

<https://www.jiuzhang.com/solution/k-substring-with-k-different-characters/>