Given a string s, find the length of the longest substring without repeating characters.

Question

Accepted Answer

The optimal solution uses the Sliding Window technique along with a HashMap to keep track of the most recent index of each character.

Two pointers, left and right, define the current window of unique characters. As the right pointer expands the window, each character is checked in the HashMap. If the character already exists within the current window, the left pointer is moved to the position immediately after the previous occurrence of that character.

The maximum window size encountered during the traversal represents the length of the longest substring without repeating characters.

This approach processes each character only once, making it highly efficient for large strings.

Java Solution:

```
import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeatingCharacters {

public static int lengthOfLongestSubstring(String input) {

Map characterIndexMap = new HashMap();

int left = 0;
        int maximumLength = 0;

for (int right = 0; right < input.length(); right++) {

char currentCharacter = input.charAt(right);

if (characterIndexMap.containsKey(currentCharacter)) {
```
                left = Math.max(
                        left,
                        characterIndexMap.get(currentCharacter) + 1
```
                );
            }

characterIndexMap.put(currentCharacter, right);
```
            maximumLength = Math.max(
                    maximumLength,
                    right - left + 1
```
            );
        }

return maximumLength;
    }

public static void main(String[] args) {

String input = "abcabcbb";

int result = lengthOfLongestSubstring(input);

System.out.println(
```
                "Length of Longest Substring: " + result
```
        );
    }
}
```
Output:
Length of Longest Substring: 3

Explanation:
The longest substring without repeating characters is "abc", which has a length of 3.

Time Complexity:
O(n), where n is the length of the string because each character is visited at most once.

Space Complexity:
O(min(n, k)), where k is the size of the character set since the HashMap stores only unique characters currently being tracked.

Key Interview Points:
• Sliding Window is the standard and most efficient approach for this problem.
• HashMap enables constant-time lookup of previously seen characters.
• Using Math.max() prevents the left pointer from moving backwards.
• A brute-force approach checks all possible substrings and requires O(n²) time complexity.