To find the longest substring with unique characters in a given string

//The technique used is "dynamic programming"
#include <stdio.h>
#include <string.h>

typedef struct {

const char *start;
size_t len;

}Substring;


Substring longestUniqueSubstring(const char *s){

Substring ret = {s, 1};

Substring cur = {s, 1}; //current unique string

size_t i, len = strlen(s);

const char *p = NULL;

for(i = 1; i < len; ++i){
 
            //include current element and check for uniqueness
p = memchr(cur.start, s[i], cur.len);

if(p){
//if not unique
if(cur.len > ret.len)
ret = cur;
 
                    //update cur           
cur.len -= (p - cur.start) + 1;

cur.start = p + 1;
}

cur.len++;

}

if(cur.len > ret.len)
ret = cur;


return ret;
}


int main(){

char s[64];

scanf("%s", s);

Substring sub = longestUniqueSubstring(s);

((char *)sub.start)[sub.len] = '';

printf("%s\n", sub.start);

return 0;

}
Advertisements

2 thoughts on “To find the longest substring with unique characters in a given string

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s