[LeetCode] 3.Longest Substring W

Welcome To My Blog

3.Longest Substring Without Repeating Characters (medium)

3.1.png

Brute solution

1. 因为Time Limit Exceeded不被AC
2. 维护两个index找出所有的window,O(n^{2),每次都检查window内的元素是否有重复,最终导致O(n}3)

3. 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

1. 采用滑动窗口(sliding window)
   By using HashSet as a sliding window, checking if a character in the current can be done in O(1).使用HashSet用空间换取时间
2. HashMap: map.containsKey(a),map.get(a),map.put(a,i)
   HashSet: set.contains(a),set.remove(a)
3. 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;
    }
}

5. 窗口状态变化图
   3.3.png
   其中,步骤2~5太多余,直接把i挪到set中重复元素的右边即可!,通过HashMap实现,下面说明

Sliding window version2

1. version1最多需要2n次循环,建立元素与索引的映射后需要n次循环即可解决
2. 具体来说就是对n个元素都进行元素值与索引的映射,如果有元素重复出现,则会更新映射
3. 测量长度的起点用索引i表示,终点用索引j表示,出现重复元素时,如果其索引大于等于i,则更新i;如果其索引小于i,则不需要更新i
4. 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

1. 这种情况下不需要字符和索引之间的映射了,直接用一个大小为128个int数组即可
2. int数组,默认初始值为0,利用这一点!HashMap没有这一特点
3. 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;
    }
}