-
Notifications
You must be signed in to change notification settings - Fork 1k
/
Longest_substring_without_repeating_chars.cpp
88 lines (76 loc) · 1.67 KB
/
Longest_substring_without_repeating_chars.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
Description :
Finding the longest substring without repeating characters having linear time Complexity O(n)
and constant Space Complexity O(1)
*/
#include <bits/stdc++.h>
using namespace std;
//length of longest substring
int Lols(char str[], int len)
{
//returning zero if the string is empty
if (str == NULL || len == 0)
{
return 0;
}
// varible for traversing in the string
int i = 0;
int j = 0;
// to store the maximum length of the substring w/o repeating Characters
int max_len = 0;
// boolean varible to check for the charecters
bool hash[256] = {0};
while (i < len)
{
if (hash[str[i]])
{
if (i - j + 1 > max_len)
{
//max_len=max(max_len,i-j+1);
max_len = i - j + 1;
}
while (str[j] != str[i])
{
hash[str[j]] = 0;
j++;
}
i++;
j++;
}
else
{
hash[str[i]] = 1;
i++;
}
}
if (max_len < len - j)
{
//max_len=max(max_len,len-j);
max_len = len - j;
}
return max_len - 1;
}
int main(void)
{
char string[20];
printf("Enter Input String:");
scanf("%[^\n]%*c", string);
// length of the string
int len = strlen(string);
printf("\nlength of longest substring without repeating characters: %d\n", Lols(string, len));
}
/*
Time complexity : O(n)
Space complexity : O(n)
*/
/*
Sample Input-output
Input: Enter Input String:abcbacbb
Output: length of longest substring without repeating charecters: 3
Input: Enter Input String:Hackincodes
Output: length of longest substring without repeating charecters: 7
Input: Enter Input String:ddddd
Output: length of longest substring without repeating charecters: 1
Input: Enter Input String:
Output: length of longest substring without repeating charecters: 0
*/