Longest substring without repeating characters

Longest sub-string without repeating characters

Common Interview Question

Problem Statement

You are given a string. You need to find the length of "longest substring with unique characters" in O(n) time.
Ex: For Hackertohacker it is 8, hackerto

Solution

#include<stdio.h>
#include<string.h>

int longestSubString(char *str);

int main()
{

char str[] = "hackertohacker";
int len = longestSubString(str);
printf("%d",len);
getchar();
}

int longestSubString(char *str)
{

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

int curr_len=1;
int max_len=1;
int len=strlen(str);

visited[str[0]]=0;
int prev;

for(i=1;i<len;i++)
{
    prev = visited[str[i]];
   
    if(prev == -1 || i-prev > curr_len)
        curr_len++;
    else {
        if(max_len < curr_len)
          max_len=curr_len;
        curr_len=i-prev;
    }
   
    visited[str[i]]=i;
}

if(max_len < curr_len)
    max_len = curr_len;

return max_len;
}       

//If you have a different approach in mind, please share it in comments section for our readers.


Time Complexity: O(n)


If you find this blog somewhat helpful, please share it and Keep Visting...:)