Maximum length of character substring

#1

Can you explain me this part how is it working
for(int i=1;i<n;i++){
int last_occ = visited[a[i]];

    //Expansion 
    if(last_occ==-1||i-current_len>last_occ){
        current_len += 1;
        //max_len = max(current_len,max_len);
    }
    //Expansion + Contraction
    else{
        if(current_len>max_len){
            max_len = current_len;
        }
        current_len = i - last_occ;
    }
    visited[a[i]] = i;
}

explain me with a test case
lets take this test case
‘abcdabcdefghi’
output should be 9

#2

Hi @Vivek-Pandey-2129725577345937,
Lets take the test case s=“abcbcad”
current_len=0, max_len=0,visited contain all -1,
now lets start for loop from i=1,

->i=1) last_occ=-1(since ‘a’ hastn’t been visited before)
so we go into if condition and current_len and max_len become 1.
visited[‘a’]=1

->i=2) last_occ=-1(since ‘b’ hasn’t been visited before)
so we go into if condition and current_len and max_len become 2.
visited[‘b’]=2

->i=3) last_occ=-1(since ‘c’ hasn’t been visited before)
so we go into if condition and current_len and max_len become 3.
visited[‘c’]=3

->i=4) last_occ=2(since b has been visited before)
so we check if i-currlen>last occ which is not case here since our max length of string is from 1 to
3. so we go into else and update currlen to i-last_occ which mean curr_len=2.
visited[‘b’]=4

->i=5)last_occ=3(since ‘c’ has been visited before)
so we check if i-currlen>last occ which is not case here since our max length of string is from 3 to
4. so we go into else and update currlen to i-last_occ which mean curr_len=2.
visited[‘c’]=5

->i=6)last_occ=1(since ‘a’ has been visited before)
so we check if i-currlen>last occ which is true since our max string is from 4 to 5 and doesn’t
contain ‘a’.
so we go into if condition and current_len and max_len become 3.
visited[‘a’]=6

->i=7)last_occ=-1(since ‘d’ hastn’t been visited before)
so we go into if condition and current_len and max_len become 4.
visited[‘d’]=7

so answer comes out to be 4.
Hope dis resolve ur doubt :slight_smile: