Maximum unique string

#1

Can you dry run this code. I have some doubts .

#2

Please share the code for which you want dry run.

#3

#include
#include
using namespace std;

int main() {
char a[] = “babbbbb”;

int n = strlen(a);
int current_len = 1;
int max_len = 1;

int visited[256];

for(int i=0;i<256;i++){
    visited[i] = -1;
}


visited[a[0]] = 0;

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;
}

 if(current_len>max_len){
            max_len = current_len;
}
cout<<max_len<<endl;


return 0;

}

#4

Code runs this way:

  1. You check the last occurence for current character and if it lies in window, then you must shrink window, then add this element to window!, else you don’t have to shrink window and you may add this letter directly to your window!
  2. Always keep a check to update maxlen.
    Some logical errors:
  3. You are not updating visited[a[i]] in case of expansion!

here you should check i-current_len+1>last_occ as this is actual start of window.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.