Length of longest substring without repeating characters
#include <bits/stdc++.h>
using namespace std;
int main(){
// make a container for keeping track of passed indices i.e. updated values of indices of chars.
// make use of two pointer by taking l,r at 0.
// keep increasing the interval in such a manner such that there is no repeating char in between the range l-r.
// to do so:
// if mpp[s[r]] != 1 and l < prev(r+1): then jump l to prev(r+1)
string s;
cin >> s;
vector<int> mpp(256, -1);
int l,r = 0;
int len = 0;
while(r != s.length()){
if(mpp[s[r]] != -1) l = max(l, mpp[s[r]] + 1); //jump l to prev r + 1
mpp[s[r]] = r; //update new value of r
len = max(len, r - l + 1);
r++; //store len and make a step
}
cout << len << endl;
return 0;
}
Comments
Post a Comment