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 <stdio.h>
2#include <string.h>
3
4int lengthOfLongestSubstring(char * s){
5 int n = strlen(s);
6 int maxLen = 0;
7 int index[128] = {0};
8 int start = 0;
9 for (int end = 0; end < n; end++) {
10 start = index[s[end]] > start ? index[s[end]] : start;
11 maxLen = (end - start + 1) > maxLen ? (end - start + 1) : maxLen;
12 index[s[end]] = end + 1;
13 }
14 return maxLen;
15}
16
17int main() {
18 printf("%d\n", lengthOfLongestSubstring("abcabcbb")); // Output: 3
19 printf("%d\n", lengthOfLongestSubstring("bbbbb")); // Output: 1
20 printf("%d\n", lengthOfLongestSubstring("pwwkew")); // Output: 3
21 return 0;
22}
23The code uses an integer array index of size 128 to store the last index + 1 of each character. We iterate end over the string, and if the character has appeared before, we move the start pointer to the right of the previous index. Then, update the maxLen if the current substring length is greater than maxLen.