## Approach 1: Sliding Window

• Time:O(n)
• Space:O(128) = O(1)

## C++

``````class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0;
int distinct = 0;
vector<int> count(128);

for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s[r]] == 1)
++distinct;
while (distinct == k + 1)
if (--count[s[l++]] == 0)
--distinct;
ans = max(ans, r - l + 1);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int ans = 0;
int distinct = 0;
int[] count = new int[128];

for (int l = 0, r = 0; r < s.length(); ++r) {
if (++count[s.charAt(r)] == 1)
++distinct;
while (distinct == k + 1)
if (--count[s.charAt(l++)] == 0)
--distinct;
ans = Math.max(ans, r - l + 1);
}

return ans;
}
}
``````

## Python

``````class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
ans = 0
distinct = 0
count = Counter()

l = 0
for r, c in enumerate(s):
count[c] += 1
if count[c] == 1:
distinct += 1
while distinct == k + 1:
count[s[l]] -= 1
if count[s[l]] == 0:
distinct -= 1
l += 1
ans = max(ans, r - l + 1)

return ans
``````

## Approach 2: Ordered Map

• Time:O(n\log k)
• Space:O(n)

## C++

``````class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0;
map<int, char> lastSeen;          // {last index: char}
unordered_map<char, int> window;  // {char: index}

for (int l = 0, r = 0; r < s.length(); ++r) {
const int inChar = s[r];
if (window.count(inChar))
lastSeen.erase(window[inChar]);
lastSeen[r] = inChar;
window[inChar] = r;
if (window.size() > k) {
const auto [lastIndex, outChar] = *begin(lastSeen);
lastSeen.erase(begin(lastSeen));
window.erase(outChar);
l = lastIndex + 1;
}
ans = max(ans, r - l + 1);
}

return ans;
}
};
``````