[Geeks for Geeks] Longest K unique characters substring

Longest K unique characters substring

Given a string you need to print the size of the longest possible substring that has exactly K unique characters. If there is no possible substring then print -1.

  • Time : O(n)
  • Space : O(1)
    • require constant space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int longestKSubstr(string s, int k) {
unordered_map<char, int> counter;
int res = -1, l = 0, r = 0, n = s.length();
while(r < n) {
if(++counter[s[r++]] == 1) k--;
if(k == 0)
res = max(res, r - l);
else {
while(l < r and k < 0) {
if(--counter[s[l++]] == 0) k++;
}
}
}
return res;
}
};

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/17/PS/GeeksforGeeks/longest-k-unique-characters-substring/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.