# Longest substring without repeat (C++)

Question : You are given a string str , you have to find the length of the longest substring which doesnot contain any repeating character.
Example : “ABDEFGABEF”, the longest substring are “BDEFGA” and “DEFGAB”, with length 6

Brute Solution :

We can get the solution by generating all the substring . Once we generate all the ssubstring we can check if the current substring is distinct or not , if it is distinct we just keep its length , and we return the answer which is maximum among all these .
Pseudo Code :

for(i=0 to n-1){
for(j=i to n-1){
if(isDistict(string,i,j)){
res=max(res,j-i+1)
}
}
}

Pseudo code for isDistinct function :

```vector<bool> visited(26);
for (int k = i; k <= j; k++) {
if (visited[str[k] - 'a'] == true)
return false;
visited[str[k] - 'a'] = true;
}
return true;```

Time Complexity : O(n^3)
Space Complexity : O(1)

Optimal Solution :

To get a better time complexity we will be using two pointers here and additional space also .
Initially we will take one left=0 pointer , one right=0 pointer , one map<char,.int> and a variable to store the longest substring’s length .

We will be iterating using the right pointer . Once we hit a character , we will check if its exist in our map or not , if it doesnot exist , we will simply insert the element to the map with its index in following way : m[str[right]]=right . After that we will be calculating the length by using the difference of left and right pointer .

Now if we our current element exist on the map already , it meant we already hit this character , so its repetitive character , so we will start our new substring using the left pointer wihtout any repeating character and update our left pointer according to that in this way : left=max(m[s[right]]+1,left); , So we going to start our next string from the next of our current character .

Example : abcabcbb , we will start left and right from first character that is a . Now we will increase our right pointer , once we find a repeating character which is already stored in our map , in this case , once right reaches 3rd index i.e. substring is abca ,we will find a charachter which is already in our map we will update left pointer.

And once we complete the iteration we will have the length of longest substring .

Code :
C++
function to find length of longest substring without repeat :

int lengthOfLongestSubstring(string s) {

``````    int left=0;
map<char,int>m;
int right=0;
int n=s.length();
int len=0;
while(right<n)
{
if(m.find(s[right])!=m.end())
{
left=max(m[s[right]]+1,left);
}

m[s[right]]=right;
len=max(len,right-left+1);
right++;

}

return len;

}``````

Time Complexity : O(n)
Space Complexity : O(1)