[Geeks for Geeks] Length of the longest substring

Length of the longest substring

Given a string S, find the length of the longest substring without repeating characters.

  • Time : O(n)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
public:
int longestUniqueSubsttr(string S){
int dup = 0, l = 0, r = 0, res = 0, n = S.length();
unordered_map<char, int> freq;

while(r < n) {
while(!dup and r < n) {
if(++freq[S[r++]] == 2) dup++;
if(!dup) res = max(res, r - l);
}
while(dup and l < r) {
if(--freq[S[l++]] == 1) dup--;
}

}

return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/22/PS/GeeksforGeeks/length-of-the-longest-substring/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.