This approach uses a two-pointer technique (often called a sliding window) to efficiently find the longest substring without repeating characters. The idea is to keep moving a start pointer to the right, while expanding the end pointer, ensuring all characters between the two pointers are unique.
Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice, once by the start pointer and once by the end pointer.
Space Complexity: O(1), since we use a fixed array of size 128 for ASCII characters.
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5using namespace std;
6
7int lengthOfLongestSubstring(string s) {
8 unordered_map<char, int> charIndex;
9 int maxLen = 0, start = 0;
10 for (int end = 0; end < s.length(); ++end) {
11 if (charIndex.find(s[end]) != charIndex.end()) {
12 start = max(start, charIndex[s[end]] + 1);
13 }
14 charIndex[s[end]] = end;
15 maxLen = max(maxLen, end - start + 1);
16 }
17 return maxLen;
18}
19
20int main() {
21 cout << lengthOfLongestSubstring("abcabcbb") << endl; // Output: 3
22 cout << lengthOfLongestSubstring("bbbbb") << endl; // Output: 1
23 cout << lengthOfLongestSubstring("pwwkew") << endl; // Output: 3
24 return 0;
25}
26This solution employs an unordered_map to store the last seen position of characters. As we iterate, if a character is found in the map, we may adjust the start of our window to ensure no repeats within the window. The longest window size is handled by updating maxLen.