Given a string **s**, the task is to find the length of the longest substring without repeating characters.

**Input:** s = "cabcabcbb"

**Output:** 3

**Input:** s = "aaaaa"

**Output:** 1

**Input:** s = "zpwwke"

**Output:** 3

## Solutions

### Method 1: In O(n^2) time and O(n) space

This problem can be solved in **O(n^2)** time and **O(n)** space with the help of a **hash**.

The idea is to use two **nested loops** and check for every substring.

Use a HashSet to identify if the current substring has a repeating character.

##### Complexity

The time complexity of this solution is **O(n^2)** and the space complexity is** O(n)**.

### Method 2: In O(n) time and O(n) space

This problem can be solved in **O(n)** time and **O(n)** space with the help of a sliding window.

The idea is to maintain a **sliding window** from the i^{th} to the j^{th} index.

Use a **HashMap** to identify if the current window has a repeating character. This map contains a character as a key and the character's index in the array as a value.

If a repeating character is found at the j^{th} index, look up the index of an already existing duplicate character in the map and move **i** to the next of this index.

While checking for repeating characters in a map, make sure that the repeating character is in the current window (at >=i^{th} index).

Keep incrementing the j^{th} index until it is less than or equals the last index and the character at the j^{th} index is not repeating.

In each iteration, if the length of the sliding window, i.e., **"lengthTillHere,"** is greater than **"lengthSoFar,"** update lengthSoFar = lengthTillHere.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is** O(n)**.