3.Longest Substring Without Repeating Characters (medium)
3.1.png
Brute solution
- 因为Time Limit Exceeded不被AC
- 维护两个index找出所有的window,O(n2),每次都检查window内的元素是否有重复,最终导致O(n3)
-
time complexity:
3.2.png
public class Solution{
public int lengthOfLongestSubstring(String s) {
int longest = 0;
for(int i=0; i<s.length()-1; i++){
for(int j=i+1;j<=s.length();j++){
if(isn_repeated(s,i,j)) longest = Math.max(longest,j-i);
else break;
}
}
return longest;
}
public boolean isn_repeated(String s,int start,int end){
Set<Character> container = new HashSet<>();
for(int i=start;i<end;i++){
char ch = s.charAt(i);
if( ((HashSet) container).contains(ch)) return false;
container.add(ch);
}
return true;
}
}
Sliding window version1
- 采用滑动窗口(sliding window)
By using HashSet as a sliding window, checking if a character in the current can be done in O(1).使用HashSet用空间换取时间 - HashMap: map.containsKey(a),map.get(a),map.put(a,i)
HashSet: set.contains(a),set.remove(a) - complexity analysis:
- time complexity:O(2n)=O(n).最坏的情况:每个元素都被i,j访问,这时便是O(2n)
- space complexity:O(min(n,m)),空间复杂度取决于窗口的长度,窗口长度的上界是字符串长度n或者charset/alphabet表m
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int res = 0, i = 0, j = 0;
while (i < n && j < n){
//如果set中不包含第j个字母,那么就把这个字母插入set
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
//记录substring的长度
res = Math.max(res,j - i);
}
//如果set中包含第j个字母,则删掉set中第一个元素,然后继续循环
else{
set.remove(s.charAt(i++));
}
}
return res;
}
}
- 窗口状态变化图
3.3.png
其中,步骤2~5太多余,直接把i挪到set中重复元素的右边即可!,通过HashMap实现,下面说明
Sliding window version2
- version1最多需要2n次循环,建立元素与索引的映射后需要n次循环即可解决
- 具体来说就是对n个元素都进行元素值与索引的映射,如果有元素重复出现,则会更新映射
- 测量长度的起点用索引i表示,终点用索引j表示,出现重复元素时,如果其索引大于等于i,则更新i;如果其索引小于i,则不需要更新i
- complexity analysis:
- time complexity:O(n)
- space complexity:O(min(x,m))
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
//1. 建立映射:元素的值与元素的索引
//在这一过程中就能找到最长的substring
Map<Character, Integer> map = new HashMap<>();
int res = 0;
//2. i是测量长度的起点,j是测量长度的终点
for (int j = 0, i = 0; j < n; j++){
if(map.containsKey(s.charAt(j)))
//如果跟i左边的元素重复了,则不更新测量起点
i = Math.max(map.get(s.charAt(j)) ,i);
//3. 这一步说明了,总共进行n次映射,如果有元素重复出现,则会更新映射
//3.1 每个元素的位置为当前索引的下一个,更新时会让i在重复元素的右边
map.put(s.charAt(j),j + 1);
//4. 跟之前的res比较,取最大的
res = Math.max(j - i + 1,res);
}
return res;
}
}
假设字符集为ASCII
- 这种情况下不需要字符和索引之间的映射了,直接用一个大小为128个int数组即可
- int数组,默认初始值为0,利用这一点!HashMap没有这一特点
- complexity analysis:
- time complexity:O(n)
- space comeplexity:O(min(n,m))
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n =s.length(),res = 0;
//int数组,默认初始值为0,利用这一点!HashMap没有这一特点
int[] index = new int[128];
//遍历每个元素,测量起点i,测量终点j
for (int j = 0, i = 0; j< n - 1; i++){
//如果当前元素已经存在于数组中,则要判断是否更新测量起点i
//通过index[j]和i的大小判断是否有重复,数组中没有该
//如果当前元素没出现过,那么index[s.charAt(j)] == 0
//如果当前元素出现过,那么index[s.charAt(j)]->0,问题来了:如果index[s.charAt(j)]<i,说明当前元素不在窗口内;如果index[s.charAt(j)]>i,说明当前元素在窗口内;边界情况:index[s.charAt(j)]==i,重复元素不在窗口内,i的值保持不变
i = Math.max(index[s.charAt(j)],i)
res = Math.max(j - i + 1,res);
// 将当前元素的值设置为其索引的右边,这个索引值是递增的
index[s.charAt(j)] = j + 1;
}
return res;
}
}
