Description:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given"abcabcbb", the answer is"abc", which the length is 3.
Given"bbbbb", the answer is"b", with the length of 1.
Given"pwwkew", 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.
Solution：
Approach 1：Brute Force [Time Limit Exeeded]
A 2-layer loop，i and j denote the start and the end of the substring. A HashSet is used to record the characters in the substring. Every time in the inner loop we check if s[j] is in the set. Once s[j] is already in the set, we break the inner loop to begin a new outer loop, or else we put it into the set and update the max.
public class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
for (int i = 0; i < s.length(); i++) {
HashSet<Character> set = new HashSet<>();
for (int j = i; j < s.length(); j++) {
if(!set.contains(s.charAt(j))) {
set.add(new Character(s.charAt(j)));
max = Math.max(max, set.size());
} else {
break;
}
}
}
return max;
}
}
Approach 2: Using HashMap with time complexity O(n)
We can use a HashMap to record the position in the substring, which would allow i straightly go behind the same character of s[j] in the substring.
public class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0;
int n = s.length();
int max = 0;
HashMap<Character, Integer> map = new HashMap<>();
for(int j = 0; j < n; j++) {
if(map.containsKey(s.charAt(j))) {
i = Math.max(i, map.get(s.charAt(j))+1); // i goes behind the the same character of s[j] in the substring
}
map.put(s.charAt(j), j); // every time we need to record the position
max = Math.max(max, j-i+1);
}
return max;
}
}
Detailed should be paid attention to as followings:
-
ican only go forward so when updatei, we do not need to change its value if the the value (index) ofs.charAt(j)in the map is lower thani(which means the value (index) is out of the current substring). - map must be updated every time we enter the loop. I have made the mistake that if the map contains
s[j]it will not be updated. After thinking for a while, I figured out that if the map containss[j],i(the start of the substring) will be update and the substring (s[i...j]) only contains ones[j]'s character. So map must be updated to record the new position ofs[j].
Approach 3: Using an array to replace HashMap with time complexity O(n)
Since we know that there are no more than 128 kinds of characters in ASCII, we could use an array to mimic the HashMap
public class Solution {
public int lengthOfLongestSubstring(String s) {
int[] c = new int[128];
int max = 0;
for(int i = 0, j = 0; j < s.length(); j++) {
i = Math.max(i, c[s.charAt(j)]);
c[s.charAt(j)] = j+1; // j+1 indicates the position right behind s[j]
max = Math.max(max, j-i+1);
}
return max;
}
}
However, I cannot convert HashMap to array. Details are as followings:
The most significant difference is when update the c array, we use j+1 to record the position, which would cooperate with the previous line i = Math.max(i, c[s.charAt(j)]);. j+1 indicates the position when i need to be updated. But why don't we let it just be j and make the previous line as i = Math.max(i, c[s.charAt(j)]+1);. Here is the issue:
When using HashMap, we update i if and only if the map contains s[j], but when using array, we update i every time we enter in the loop, which would cause a problem when the character is first appear in the string.
So imagine the situation that the string itself is the wanted string, but i will be updated to 1 because all the entry value of the array c is 0, and c[s.charAt(j)]+1 will be 1. We can solve the problem in 2 ways:
- If we add a
ifclauseif (c[s.charAt(j)] != 0)to decide whether to updatei, then thei = Math.max(i, c[s.charAt(j)]+1);will work. - Additionally, we can also let the all the initial entry value of array
cto be -1, which will also well handle the issue.
