-
-
Notifications
You must be signed in to change notification settings - Fork 7.3k
/
longest_substring_without_repeating_characters.cpp
110 lines (98 loc) · 3.73 KB
/
longest_substring_without_repeating_characters.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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/**
* @file
* @brief Solution for Longest Substring Without Repeating Characters problem.
* @details
* Problem link: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
*
* Intuition:
* 1) The intuition is straightforward and simple. We track the frequency of characters.
* 2) Since we can't use a string to track the longest substring without repeating characters efficiently (as removing a character from the front of a string isn't O(1)), we optimize the solution using a deque approach.
*
* Approach:
* 1) Initialize an unordered_map to track the frequency of characters.
* 2) Use a deque for pushing characters, and update the result deque (`res`) with the current deque (`temp`)
* whenever we find a longer substring.
* 3) Use a while loop to reduce the frequency from the front, incrementing `i`,
* and removing characters from the `temp` deque as we no longer need them.
* 4) Return `res.size()` as we are interested in the length of the longest substring.
*
* Time Complexity: O(N)
* Space Complexity: O(N)
*
* I hope this helps to understand.
* Thank you!
* @author [Ashish Kumar Sahoo](github.com/ashish5kmax)
**/
#include <iostream> // for IO Operations
#include <unordered_map> // for std::unordered_map
#include <deque> // for std::deque
#include <string> // for string class/string datatype which is taken as input
#include <cassert> // for assert
/**
* @class Longest_Substring
* @brief Class that solves the Longest Substring Without Repeating Characters problem.
*/
class Longest_Substring {
public:
/**
* @brief Function to find the length of the longest substring without repeating characters.
* @param s Input string.
* @return Length of the longest substring.
*/
int lengthOfLongestSubstring(std::string s) {
// If the size of string is 1, then it will be the answer.
if (s.size() == 1) return 1;
// Map used to store the character frequency.
std::unordered_map<char, int> m;
int n = s.length();
// Deque to remove from back if repeating characters are present.
std::deque<char> temp;
std::deque<char> res;
int i, j;
// Sliding window approach using two pointers.
for (i = 0, j = 0; i < n && j < n;) {
m[s[j]]++;
// If repeating character found, update result and remove from the front.
if (m[s[j]] > 1) {
if (temp.size() > res.size()) {
res = temp;
}
while (m[s[j]] > 1) {
temp.pop_front();
m[s[i]]--;
i++;
}
}
// Add the current character to the deque.
temp.push_back(s[j]);
j++;
}
// Final check to update result.
if (temp.size() > res.size()) {
res = temp;
}
return res.size(); // Return the length of the longest substring.
}
};
/**
* @brief Self-test implementations
* @returns void
*/
static void tests() {
Longest_Substring soln;
assert(soln.lengthOfLongestSubstring("abcabcbb") == 3);
assert(soln.lengthOfLongestSubstring("bbbbb") == 1);
assert(soln.lengthOfLongestSubstring("pwwkew") == 3);
assert(soln.lengthOfLongestSubstring("") == 0); // Test case for empty string
assert(soln.lengthOfLongestSubstring("abcdef") == 6); // Test case for all unique characters
assert(soln.lengthOfLongestSubstring("a") == 1); // Single character
std::cout << "All test cases passed!" << std::endl;
}
/**
* @brief Main function.
* @return 0 on successful execution.
*/
int main() {
tests(); // run self-test implementations
return 0;
}