Write a C program for longest substring without repeating characters. For example if the string is “abcdabc” the longest substring without repeating is “abcd” of length 4.

C program for longest substring without repeating characters

  • The problem is to find the length of substring without repeating character.
  • To identify repeat of a character take a integer array of length 256. int freq[256].
  • whenever a character is found increase its frequency. Like if char *s then freq[*s]++.
  • Let us observer our input “abcdabc”.
  • First find length of substring without repeat in “abcdabc” and save the max length.
  • Again First find length of substring without repeat in “bcdabc” and save the max length
  • Repeat this procedure until string “abcdabc” ends.
#include <stdio.h>
#include<malloc.h>

int freq [ 256];
int maxlen = 0;
int len(char*s)
{
	char* p;
	char* q;
	p = q = s;
	int substringfound = 0;
	//search for substring
	while (!substringfound)
	{
		// iterate over substring
	    while(!substringfound)
	    {
	    	freq[*q]++;
	    	if(freq[*q] == 1 || *q == '\0')
	    	{
	    	    int len = q - p;
	    	    if(maxlen < len)
	    	    	maxlen = len;

	    	    // reset freq
	    	    for (int i = 0; i < 255; i++)
	    	    	freq [ i] = -1;

	    	    if(*q == '\0')
	    	    {
	    	    	substringfound = 1;
	    	    }
	    	    break;
	    	}

	    	q++;
	    }
		p++;
		q=p;
	}
return maxlen;
}
int lengthOfLongestSubstring(char* s)
{
	for (int i = 0; i < 255; i++)
		freq [ i] = -1;
	int l = len(s);
	maxlen = 0;
	return l;
}

int main()
{
	char* s = "abcdabc";
	printf("%d\n", lengthOfLongestSubstring(s));
	return 0;
}

#gcc sample.c -osample

#./sample

4

Note: submit article at myarticle@wikistack.com to help others.



Related Contents to follow