You are given a string `S` consisting of lowercase English letters. Your task is to find the longest substring `T` of `S` that satisfies the following conditions:
- `T` contains at most `K` distinct characters.
- The length of `T` is maximized.

Write a function `get_longest_substring(S: str, K: int) -> str` that takes in a string `S` and an integer `K` as parameters and returns the longest substring `T` that satisfies the conditions.

**Examples**
```
get_longest_substring("abccbbbda", 2) => "bccbbbd"
get_longest_substring("abcdefghij", 3) => "abcdefghij"
get_longest_substring("aabbcdefffg", 4) => "aabbcdefff"
```

**Note**
- In the first example, the longest substring with at most 2 distinct characters is "bccbbbd".
- In the second example, all characters in the string are distinct, so the entire string is the longest substring.
- In the third example, the longest substring with at most 4 distinct characters is "aabbcdefff".
user
Sure, I'd be happy to help with a Python function that satisfies the given requirements. Here's a simple implementation using the `collections` module to count the characters in a substring:

```python
from collections import Counter

def get_longest_substring(s: str, k: int) -> str:
    longest_sub = ""

    # Define a sliding window function to check for unique substring length
    def check_substring(s, k, end_idx):
        count = Counter(s[:end_idx]) # Convert a string into a dictionary of long count
        # keep removing count from right of substring
        while count and end_idx - count[list(count.keys())[0]] > 0:
            count.pop(list(count.keys())[0]) # Remove the least frequent element
        return count <= k

    # Two pointers approach
    left = 0
    for right, ch in enumerate(s):
        while len(set(s[left:right+1])) > k:
            s.pop(left)
            left += 1
        while check_substring(s[left:right+1], k, right) is False:
            s.pop(left)
            left += 1
        longest_sub = max(longest_sub, s[left:right+1], key=len)

    return longest_sub
```

This function defines a sliding window technique where we move our window over the string. The two other pointers check if the remaining substring has at most K unique characters. If yes, we extend our maximum substring.

I hope this helps! Let me know if you have any additional requests.
assistant
You are given a string `S` consisting of lowercase English letters. Your task is to find the longest substring `T` of `S` that satisfies the following conditions:
- `T` contains at most `K` distinct characters.
- The length of `T` is maximized.

Write a function `get_longest_substring(S: str, K: int) -> str` that takes in a string `S` and an integer `K` as parameters and returns the longest substring `T` that satisfies the conditions.

**Examples**
```
get_longest_substring("abccbbbda", 2) => "bccbbbd"
get_longest_substring("abcdefghij", 3) => "abcdefghij"
get_longest_substring("aabbcdefffg", 4) => "aabbcdefff"
```

**Note**
- In the first example, the longest substring with at most 2 distinct characters is "bccbbbd".
- In the second example, all characters in the string are distinct, so the entire string is the longest substring.
- In the third example, the longest substring with at most 4 distinct characters is "aabbcdefff".
user
Here's a Python function that implements the sliding window technique to solve this problem:

```python
def get_longest_substring(S: str, K: int) -> str:
    start = max_length = 0
    end = -1
    current_length = 0
    char_count = {}  # dictionary to count the occurrences of each character
    result = ""

    while end < len(S) - 1:
        end += 1
        right_char = S[end]
        char_count[right_char] = char_count.get(right_char, 0) + 1
        current_length = end - start + 1

        while len(char_count) > K:
            left_char = S[start]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            start += 1
            current_length -= 1

        if current_length > max_length:
            max_length = current_length
            result = S[start:end + 1]

    return result
```

Explanation of the function:

1. Initialize two pointers `start` and `end` to represent the window.
2. Initialize an empty dictionary `char_count` to store the count of each character in the current window.
3. Iterate through the string using the `end` pointer and maintain the window such that it contains at most `K` distinct characters, by:
   - Adding characters to the right of the window (incrementing the `end` pointer).
   - If the number of distinct characters in the window is greater than `K`, remove characters from the left of the window (incrementing the `start` pointer) until there are at most `K` distinct characters left.
4. Update the `max_length` and `result` whenever a new longest substring is found.
5. Return the `result` once the iteration is complete.

Time complexity of the function: O(N), where N is the length of the input string `S`. Space complexity: O(K), where K is the maximum number of distinct characters allowed.
assistant