Longest Substring Without Repeating Characters

Given a string s, find the length of the 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.

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.

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.

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