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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int LengthOfLongestSubstring(string s) {
6 Dictionary<char, int> charIndex = new Dictionary<char, int>();
7 int maxLen = 0, start = 0;
8 for (int end = 0; end < s.Length; end++) {
9 if (charIndex.ContainsKey(s[end])) {
10 start = Math.Max(start, charIndex[s[end]] + 1);
11 }
12 charIndex[s[end]] = end;
13 maxLen = Math.Max(maxLen, end - start + 1);
14 }
15 return maxLen;
16 }
17
18 public static void Main(string[] args) {
19 Solution sol = new Solution();
20 Console.WriteLine(sol.LengthOfLongestSubstring("abcabcbb")); // Output: 3
21 Console.WriteLine(sol.LengthOfLongestSubstring("bbbbb")); // Output: 1
22 Console.WriteLine(sol.LengthOfLongestSubstring("pwwkew")); // Output: 3
23 }
24}
25Using a dictionary in C#, we map characters to their last index. We adjust the start pointer when a duplicate character is processed, ensuring the active window always has unique characters.