# Longest Substring Without Repeating Characters

**Example 1:**

```
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```

**\*\*Tip: To implement an efficient solution, we will use the Sliding Window approach.** 

***A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. \[ i , j ) \[i,j) (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide \[ i , j ) \[i,j) to the right by 1 element, then it becomes \[ i + 1 , j + 1 ] (left-closed, right-open).***

### **Approach1: Brute Force** 

As we think on a more optimal approach to solve this problem, an evident but also intuitive approach would be the following:

* Iterate through the characters of the String.
* For each Iteration I, we check whether `String[i,j]` is unique. in the advent that it is, we update our `max` variable if it is the longest unique Substring that we've encountered so far.

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
       int max = 0;
        
        for(int i = 0; i < s.length(); i++){
            for(int j = i + 1; j <= s.length(); j++){
                if(isUnique(s, i, j)){
                    max = Math.max(max, j - i);
                }
            }
        }
        return max;
    }
    private boolean isUnique(String s, int low, int high){
        Set<Character> set = new HashSet<>();
        for(int i = low; i < high; i++){
            if(!set.add(s.charAt(i)))
                return false;
        }
        return true;
    }
}
```

**`Time: O(n3)                Space: O(1)`**

### **Approach2: Efficient**

Unfortunately, the above approach is too slow hence we need to optimize it. An efficient approach we can think of is by using the properties of a set ***to** simulate a sliding window* by doing the following:

* We start with a window\[i,j] with i and j = 0;
* We slide j to the right every time a character is not in the set. We do so until we encounter a Character j that is already in the Set. At this point, we would have found the longest unique character String.
* If we encounter a character that is already present in the set, we slide the window by augmenting i.

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int max = 0, i = 0, j = 0;
        
        while(j < s.length()){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                max = Math.max(max, j - i);
            }
            else{
                set.remove(s.charAt(i++));
            }
        }
        return max;
    }
}
```

**`Time: O(n)                Space: O(k)  k = distinct characters`**

Approach2: Optimal

The above solution required 2n steps as in the worst case, we visited each character twice. Instead of using a set, we can essentially map a character to it's index. Now, if we again encounter this character and it was at position i, we would skip to i + 1.

* Move a right pointer to scan through the string and update it's corresponding Key and Values
* If Character is already in the hashmap, updfate the left pointer to the right of where this character was originally found to skip over it.

```java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        for(int i = 0, j = 0; j < s.length(); j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i, map.get(s.charAt(j)) + 1);
            }
            max = Math.max(max, j - i + 1);
            map.put(s.charAt(j), j);
        }
        return max;
    }
}
```

**`Time: O(n)                Space: O(k)  k = distinct characters`**