Find max size of a sub-string, in which no duplicate chars present

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

For example:

Input: s = "procodr"
Output: Longest substring: 4
There are two substrings with length 4 that have no repeating characters:
      - proc
      - codr

Method 1: The naive approach is to consider all substrings one by one and check whether each substring contains all unique characters or not. There will be total n*(n+1)/2 substrings (n = length of string). Whether a substirng contains all unique characters or not can be checked in linear time by scanning it from left to right and keeping a map of visited characters.

Time Complexity: O(n³)

Method 2:

#include <bits/stdc++.h>
using namespace std;

/* function to return the max len of substring */
int maxLen(string s)
{
    int len = s.length();

    /* map to store the last position of characters */
    map<int ,int> lst;
    
    /* marking the first character as visited */
    lst[s[0]-'0'] = 0;

    int lst_pos, max_len=1, cur_len=1;

    /* start from second character as first element is already processed */
    for(int i = 1; i<len; i++)
    {
        /* if the current char is not present in the already process
           substring or it is not the part of Non-Repeating Character
           Substring (NRCS) processed so far, increment cur_len++ */
        if(!lst[s[i]-'0'] || (i - lst[s[i]-'0']) > cur_len)
            cur_len++;

        /* If the current character is present in currently
           considered NRCS, then update NRCS to start from
           the next character of previous instance. */
        else
        {
            /* when we change the NRCS, we should check if cur_len is 
               smaller or greater than max_len */
            max_len = max(max_len, cur_len);
            cur_len = i - lst_pos; 
        }

        /* marking the position of current element */
        lst[s[i]-'0']=i;
    }

    /* making final updation of max_len */
    max_len = max(max_len, cur_len);
    
    return max_len;
}

/* driver function */
int main()
{
    string s = "procodr";

    cout<<"Max len = "<<maxLen(s)<<"\n";

    return 0;
}

Output:

Max length = 4

Time Complexity: O(n)