Program Discussion :: Strings
83 / 60
Write code to find the largest substring of a given string without repeating characters.
Answer:
#include
#include
#include
#include
using namespace std;
#define NO_OF_CHARS 256
int min(int a, int b);
int longestUniqueSubsttr(char *str)
{
int n = strlen(str);
int cur_len = 1; /* lenght of current substring*/
int max_len = 1; /* result*/
int prev_index; /* previous index*/
int i;
int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
for (i = 0; i < NO_OF_CHARS; i++)
visited[i] = -1;
visited[str[0]] = 0;
for (i = 1; i < n; i++)
{
prev_index = visited[str[i]];
if (prev_index == -1 || i - cur_len > prev_index)
cur_len++;
else
{
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - prev_index;
}
visited[str[i]] = i;
}
if (cur_len > max_len)
max_len = cur_len;
free(visited); // free memory allocated for visited
return max_len;
}
int min(int a, int b)
{
return (a>b)?b:a;
}
int main()
{
char str[] = "ABDEFGABEF";
cout
Asked In ::
Language:
Arvind Singh
7 Jul, 2017 9:30 AM
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define NO_OF_CHARS 256
int min(int a, int b);
int longestUniqueSubsttr(char *str)
{
int n = strlen(str);
int cur_len = 1; // lenght of current substring
int max_len = 1; // result
int prev_index; // previous index
int i;
int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
for (i = 0; i < NO_OF_CHARS; i++)
visited[i] = -1;
visited[str[0]] = 0;
for (i = 1; i < n; i++)
{
prev_index = visited[str[i]];
if (prev_index == -1 || i - cur_len > prev_index)
cur_len++;
else
{
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - prev_index;
}
visited[str[i]] = i;
}
if (cur_len > max_len)
max_len = cur_len;
free(visited); // free memory allocated for visited
return max_len;
}
int min(int a, int b)
{
return (a>b)?b:a;
}
int main()
{
char str[] = "ABDEFGABEF";
printf("The input string is %s n", str);
int len = longestUniqueSubsttr(str);
printf("The length of the longest non-repeating "
"character substring is %d", len);
return 0;
}
Language:
Varuna Rai
7 Jul, 2017 9:30 AM
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
int min(int a, int b);
int longestUniqueSubsttr(char *str)
{
int n = strlen(str);
int cur_len = 1; /* lenght of current substring*/
int max_len = 1; /* result*/
int prev_index; /* previous index*/
int i;
int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
for (i = 0; i < NO_OF_CHARS; i++)
visited[i] = -1;
visited[str[0]] = 0;
for (i = 1; i < n; i++)
{
prev_index = visited[str[i]];
if (prev_index == -1 || i - cur_len > prev_index)
cur_len++;
else
{
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - prev_index;
}
visited[str[i]] = i;
}
if (cur_len > max_len)
max_len = cur_len;
free(visited); // free memory allocated for visited
return max_len;
}
int min(int a, int b)
{
return (a>b)?b:a;
}
int main()
{
char str[] = "ABDEFGABEF";
cout<<"The input string is" <<str;
int len = longestUniqueSubsttr(str);
cout<<"The length of the longest non-repeating "
"character substring is "<<len;
return 0;
}