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