# 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/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/string/k-substring-with-k-different-characters.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.