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){

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 :
function to find length of longest substring without repeat :

int lengthOfLongestSubstring(string s) {

    int left=0;
    int right=0;
    int n=s.length();
    int len=0;



    return len;


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

Partner Sites




Be the first to comment

Leave a Reply

Your email address will not be published.