LeetCode - Longest Substring Without Repeating Characters
Problem description
Given a string, find the length of the longest substring without repeating characters.
Example 1:
1
2
3
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
1
2
3
4
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.
Analysis
the first thought is to use a sliding window algorithms, which is to use a HashSet to store current substring, if it meets requirements, then update the variable which store max length of the substring, else the start position should be updated.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class LongestSubstringWithoutRepeatingCharacters {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0){
return 0;
}
int maxLen = 0;
HashSet<Character> set = new HashSet<>();
int start=0, end=0;
while (end < s.length()){
char c = s.charAt(end);
if (!set.contains(c)){
set.add(c);
maxLen = Math.max(maxLen, set.size());
end++;
}
else {
while (s.charAt(start) != c){
char c2 = s.charAt(start);
set.remove(c2);
start++;
}
char c2 = s.charAt(start);
set.remove(c2);
start++;
}
}
return maxLen;
}
}
However, there are some other solutions, the basic idea is to store the last seen character.
Here’s the most common one:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0)
return 0;
int j=0;
int max = Integer.MIN_VALUE;
Map<Character, Integer> hmap = new HashMap<>();
for(int i=0; i<s.length(); i++)
{
if(hmap.containsKey(s.charAt(i)))
j = Math.max(j, hmap.get(s.charAt(i)) + 1);
hmap.put(s.charAt(i), i);
int len = i-j+1;
max = Math.max(max, len);
}
return max;
}
}
A simplified solution is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] lastValidPos = new int[128];
int longestSubstringLength = 0;
int rightmostStartingPos = 0; // start position of substring
for(int i=0; i<s.length(); i++) {
char curChar = s.charAt(i);
// Consider all characters, not just the current one
rightmostStartingPos = Math.max(rightmostStartingPos, lastValidPos[curChar - ' ']);
longestSubstringLength = Math.max(longestSubstringLength, i - rightmostStartingPos + 1);
lastValidPos[curChar - ' '] = i + 1;
}
return longestSubstringLength;
}
}
What to improve
-
need to analysis the problem first and consider whether we can use the template for sliding window
-
summarize the template of substring/sliding window