Given a string, find the length of the longest substring T that contains at mostkdistinct characters.

This question could be solved with two pointers and more importantly, using the Ordered Dictionary would be able to achieve O(n) time complexity.

#### Two pointers

With two pointers `i`

and `j`

, we can explore the string using `j`

while marking the left boundary with `i`

such that `s[i..j]`

contains at most k distance characters. We would record the **rightmost** position for each character in `s[i..j]`

using a hashmap and, when the number of distinct characters exceeds `k`

, i.e., becomes `k+1`

, we need to find the **leftmost** character in the hashmap.

The time complexity would be O(nk) as for each character we would search the hashmap of size O(k).

```
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
n = len(s)
if not k or not n:
return 0
l = r = ret = 0
hashmap = {}
while r < n:
hashmap[s[r]] = r
r += 1
if len(hashmap) > k:
leftmost = n
for c in hashmap:
leftmost = min(leftmost,hashmap[c])
l = leftmost+1
del hashmap[s[leftmost]]
ret = max(ret,r-l)
return ret
```

#### Optimization with the Ordered Dictionary

However, to achieve O(n) time complexity, we need the Ordered Dictionary. It remembers the order of insertion/deletion and therefore allows us to find the first/last inserted item in O(1) time. More info about the Ordered Dictionary could be found at:

- https://www.geeksforgeeks.org/ordereddict-in-python/
- https://docs.python.org/3/library/collections.html#collections.OrderedDict

Hence, we can let the order in the ordered dictionary to be the relative positions of each item – when we meet a duplicated character, we could update its value by deleting and re-inserting, thus the first item in it is always the leftmost one.

```
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
n = len(s)
if not k or not n:
return 0
l = r = ret = 0
hashmap = collections.OrderedDict()
while r < n:
if s[r] in hashmap:
del hashmap[s[r]]
hashmap[s[r]] = r
r += 1
if len(hashmap) > k:
_,del_idx = hashmap.popitem(last=False)
l = del_idx+1
ret = max(ret,r-l)
return ret
```