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.
1import java.util.HashMap;
2
3class Solution {
4 public int lengthOfLongestSubstring(String s) {
5 HashMap<Character, Integer> map = new HashMap<>();
6 int maxLen = 0, start = 0;
7 for (int end = 0; end < s.length(); end++) {
8 if (map.containsKey(s.charAt(end))) {
9 start = Math.max(start, map.get(s.charAt(end)) + 1);
10 }
11 map.put(s.charAt(end), end);
12 maxLen = Math.max(maxLen, end - start + 1);
13 }
14 return maxLen;
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 System.out.println(sol.lengthOfLongestSubstring("abcabcbb")); // Output: 3
20 System.out.println(sol.lengthOfLongestSubstring("bbbbb")); // Output: 1
21 System.out.println(sol.lengthOfLongestSubstring("pwwkew")); // Output: 3
22 }
23}
24In this Java solution, a HashMap is employed to track the index of each character in the input string. The presence of any repeating character will update the start pointer to the right of its last seen position.