Sunday 23 December 2012

Find Length of longest substring without repeating characters in O(n). eg if string is "HELLOWORLD" then output is "WORLD" len = 5


#include<iostream.h>
#include<conio.h>
#include<string.h>

int nrcs(char *str)
{
    int n = strlen(str);
    int scan[256];
    for(int i =0; i<256 ;i++)
            scan[i]=-1;
   
    int curLen=1, maxLen=1, prev;
    scan[str[0]]=-1;
   
    int start=0,s=0,end=n-1,e;
   
    for(int i=1; i<n ;i++)
    {
            prev = scan[str[i]];
            if( prev ==-1 || i - curLen > prev)
                curLen++;
            else
            {
                    start=s;
                    end =e;
                    s = prev+1;
                    e=s;
                   
                    if(curLen > maxLen)
                    {
                           maxLen = curLen;
                    }
                    curLen = i - prev;
            }
            scan[str[i]]=i;
            e=i;
    }
    if(curLen > maxLen)
                       maxLen = curLen;
    if(e-s  >end - start)
    {
               start=s;
               end=e;
    }
    for(int j = start; j<= end ; j++)
            cout<<"\n"<<j-start+1<<" "<<str[j];
    return maxLen;
}

int main()
{
    char *str = "helloworld";
    cout<<"\n\nlen is "<<nrcs(str);
    getch();
}