Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

Input: "bbbbb" 
Output: 1 
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew" 
Output: 3 
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Bruteforce Solution

The BruteForce solution is to find all the substrings in the string and then check if they contain unique characters and updating the result with maximum of result and substring’s length. Finding all substrings of the strings require two loops and so that itself will be O(n^2). Checking if the founded substring is unique is another O(n) and so total time complexity is O(n^3), n being length of string.

As we are using a HashSet to store the letters of the substring, the space complexity will be O(n), n being length of string.

 

/*
Time Complexity - O(n^3)
Space Complexity - O(n)
*/

class LengthOfLongestSubStringBrute {
    
    public int lengthOfLongestSubstring(String s) {
        
        //Initialize the length of result substring with zero
        int ans = 0;
        
        //Loop i from 0 to length of string and
        //loop j from i+1 to length of string 
        //to get each and every substring 
        for(int i = 0; i < s.length(); i++){
            for(int j = i+1; j <= s.length(); j++){
                
                //Check if substring has all unique characters
                if(findIfUniqueSubstring(s, i, j)){
                    
                    //Update the result with the length of current substring
                    ans = Math.max(ans, j - i);
                }
            }
        }
        
        //return the answer
        return ans;
    }
    
    public boolean findIfUniqueSubstring(String s, int start, int end){
        
        //Initialize a HashSet to store the characters
        HashSet<Character> set = new HashSet<Character>();
        
        //Loop from starting index to ending index
        for(int i = start; i < end; i++){
            char c = s.charAt(i);
            
            //if the set contains present character then return false
            //else add the character to set.
            if(set.contains(c))
                return false;
            set.add(c);
        }
        
        //if all characters in substring are uniuq, return true;
        return true;
    }
}

Optimized Solution 1

Using HashSet as sliding window we can reduce the complexity from O(n^3) to O(n).

We start both i and j from 0. Add the jth character to HashSet if it is not present and update length to maximum of length and (j-i). Increment j. If jth character is present in HashSet, we remove the ith character and increment i. We continue this until both i and j are less than input length. The time and space complexity for this solution is O(n)

 

/* 
Time Complexity - O(n)
Space Complexity - O(n)
*/

class LengthOfLongestSubstringOptimized {
    
    public int lengthOfLongestSubstring(String s) {
        
        //Initialize the length of result substring with zero
        int ans = 0, i = 0, j = 0;
        
        //Initialize a HashSet to store the characters
        HashSet<Character> set = new HashSet<Character>();
        
        //Loop i from 0 to length of s and
        //loop j from 0 to length of s 
        //to get each and every substring 
        while(i < s.length() && j < s.length()){
            
            //if character at jth position is not present in set
            if(!set.contains(s.charAt(j))){
                
                //add the character to the set and set result 
                //to length of substring till now.
                set.add(s.charAt(j++));
                ans = Math.max(ans, j-i);
            }
            else{
                //remove the character at ith position and increment i;
                set.remove(s.charAt(i++));
            }
        }
        //return the answer
        return ans;
    }
        
        
}

Optimized Solution 2

This solution uses HashMap instead of HashSet. The time and space complexity is still O(n). Here we store the index of current character in hashmap. If we encounter a repeat character we update the value of i to the maximum of i and current characters(jth) index.

/* 
Time Complexity - O(n)
Space Complexity - O(n)
*/

class LengthOfLongestSubstringOptimized2 {
    
    public int lengthOfLongestSubstring(String s) {
        
        //Initialize the length of result substring with zero
        int ans = 0, i = 0, j = 0;
        
        //Initialize a HashMap to store the characters
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        //loop j from 0 to length of s 
        //to get each and every substring 
        for(j = 0; j < s.length(); j++){
            
            //if map contains jth character
            if(map.containsKey(s.charAt(j))){
                //update i to the index of 
                i = Math.max(i, map.get(s.charAt(j)));
            }
            
            //put the character in map with index
            map.put(s.charAt(j), j+1);
            ans = Math.max(ans, j-i+1);
        }
        
        //return the answer
        return ans;
    }
        
        
}

Source – LeetCode

SourceCode – Github