LongestSubstringWithoutRepeatingCharacters [source code]


public class LongestSubstringWithoutRepeatingCharacters {
static
/******************************************************************************/
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length () <= 1)
            return s.length ();
        int[] counts = new int[256];
        char[] chs = s.toCharArray ();
        int i = 0, j = 1, max_len = 0;
        counts[chs[i]]++;
        while (j < chs.length) {
            char peek = chs[j];
            if (counts[peek] == 1) {
                if (j - i > max_len)
                    max_len = j - i;
                while (peek != chs[i]) {
                    counts[chs[i]]--;       // easy to forget in refund process.
                    i++;
                }
                i++;
                if (j < i)
                    j = i;
            } else {
                counts[peek]++;
            }
            j++;
        }
        return Math.max (max_len, j - i);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingCharacters.Solution tester = new LongestSubstringWithoutRepeatingCharacters.Solution();
        String[] inputs = {
            "abcabcbb", "abc", "3",
            "bbbbb", "b", "1",
            "pwwkew", "wke", "3",
            "au", "", "2",
            "aab", "", "2",
            "tmmzuxt", "", "5",
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String s = inputs[3 * i];
            int ans = Integer.parseInt (inputs[3 * i + 2]);
            System.out.println (Printer.separator ());
            int output = tester.lengthOfLongestSubstring (s);
            System.out.printf ("%s -> %s, expected: %d\n",
                s, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }

    static String printCounts (int[] counts) {
        StringBuilder sb = new StringBuilder ();
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                sb.append (String.format ("[%c = %d], ", (char) i, counts[i]));
            }
        }
        return sb.toString ();
    }
}

感觉像是一个sliding window的题目, 但是不记得sliding window怎么写了, 随便谢谢看先;

最后还是有惊无险的做出来了, 速度是49ms (85%), 虽然是很老的题目, 但是能做到这个速度, 说明这个题目应该还是有不如sliding window的笨办法的;

在写的过程当中, 也是回忆各种sliding window算法的细节, 有一些总结;

首先, 关于题目本身, 这个题目本身并没有给过你条件说所有的char都是小写字母, 但是我当时也是一厢情愿的认为肯定全都是lowercase, 毕竟这种小的差别有什么意义呢对吧, 只要能在lowercase的范畴内写对, 那么肯定在所有的asicii范围内也没有问题;

然而算法面试就是算法面试, 这种阅读题目细节的能力也是要考察的能力之一, 最后的结果就是实际上还真的就是有全ASICII范围内的case来break掉了我原来的写法;

当然, 需要的改动其实不大, 而且因为现在是全ASICII, 所以不用像写字母的时候, 还要自己加一个shift/offset; 当然, 一个需要掌握的技巧其实就是ASICII int和char本身之间的相互转化; 当然这个其实一点不难, 两个方向都是一个case都能解决的;

关于sliding window, 这个是以前学习过的一个算法, 算法本身是有点复杂的, 为了避免在实现的时候犯错, 自己要注意记忆一个固定的套路和写法, 我记得当时记忆的那个写法的几个细节要素在于:

  • j虽然在iteration开头没有++, 但是j实际上始终是一个peek的位置; 他的++是在上一个iteration的末尾进行的, 所以实际上我们还并没有处理j. 作为一个peek位置的意思就是, j位置的element实际上是还不在window里面的; 只有你完成妥善的i操作之后, 才能把j当成自己人;
  • 循环开始之前, 我们是从[0]位置开始, 而不是从类似pre head的位置开始的, 所以你要对window进行一个初始化, 在上面的代码里面有体现;
  • 在refund的过程当中, 不要粗心, 上面代码当中有comment;
  • 这种做法的sliding window严格意义上是一个分段算法, 所以要注意一个收尾问题, 所幸这个收尾问题在这个问题的context下并不复杂;

editorial

Approach #1 Brute Force [Time Limit Exceeded]

public class Solution {  
    public int lengthOfLongestSubstring(String s) {  
        int n = s.length();  
        int ans = 0;  
        for (int i = 0; i < n; i++)  
            for (int j = i + 1; j <= n; j++)  
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);  
        return ans;  
    }  

    public boolean allUnique(String s, int start, int end) {  
        Set<Character> set = new HashSet<>();  
        for (int i = start; i < end; i++) {  
            Character ch = s.charAt(i);  
            if (set.contains(ch)) return false;  
            set.add(ch);  
        }  
        return true;  
    }  
}

这个暴力做法的思路还是很直接的, generate and test; 注意最后的复杂度是N^3;

Approach #2 Sliding Window [Accepted]

public class Solution {  
    public int lengthOfLongestSubstring(String s) {  
        int n = s.length();  
        Set<Character> set = new HashSet<>();  
        int ans = 0, i = 0, j = 0;  
        while (i < n && j < n) {  
            // try to extend the range [i, j]  
            if (!set.contains(s.charAt(j))){  
                set.add(s.charAt(j++));  
                ans = Math.max(ans, j - i);  
            }  
            else {  
                set.remove(s.charAt(i++));  
            }  
        }  
        return ans;  
    }  
}

注意, 他这个sliding window和我的写法还是有很多的共同之处的, 比如他这个try to extend表达的就很精髓, j就可以认为是一个try position. 当然, 他最后算法本身的写法和我还是有点区别的, 他的这个写法就是我常见的分段算法中的alternative, 也就是不用switch-based.

其实掌握哪一种都无所谓, 关键是细节掌握到位就行了;

Approach #3 Sliding Window Optimized [Accepted]

public class Solution {  
    public int lengthOfLongestSubstring(String s) {  
        int n = s.length(), ans = 0;  
        Map<Character, Integer> map = new HashMap<>(); // current index of character  
        // try to extend the range [i, j]  
        for (int j = 0, i = 0; j < n; j++) {  
            if (map.containsKey(s.charAt(j))) {  
                i = Math.max(map.get(s.charAt(j)), i);  
            }  
            ans = Math.max(ans, j - i + 1);  
            map.put(s.charAt(j), j + 1);  
        }  
        return ans;  
    }  
}

这个思路很有意思, 难怪叫做optimized, 这个不是标准的sliding window, 因为标准的sliding window算法是比较依赖类似counts类信息的; 这里的这个history记录的实际上是index; 当我们记录这个之后, 整个移动的过程就简单很多; 

public class Solution {  
    public int lengthOfLongestSubstring(String s) {  
        int n = s.length(), ans = 0;  
        int[] index = new int[128]; // current index of character  
        // try to extend the range [i, j]  
        for (int j = 0, i = 0; j < n; j++) {  
            i = Math.max(index[s.charAt(j)], i);  
            ans = Math.max(ans, j - i + 1);  
            index[s.charAt(j)] = j + 1;  
        }  
        return ans;  
    }  
}

这个是用array优化过之后的;

另外他这里还提到了一下, 说是ASICII其实是到128为止, 以上到256的, 是叫做extended ASICII;

discussion最优解:

@cbmbbz said in 11-line simple Java solution, O(n) with explanation:

the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward. 

       public int lengthOfLongestSubstring(String s) {  
            if (s.length()==0) return 0;  
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
            int max=0;  
            for (int i=0, j=0; i<s.length(); ++i){  
                if (map.containsKey(s.charAt(i))){  
                    j = Math.max(j,map.get(s.charAt(i))+1);  
                }  
                map.put(s.charAt(i),i);  
                max = Math.max(max,i-j+1);  
            }  
            return max;  
        }

跟editorial3类似的解法, 解释的也很详细, 甚至看起来他根本就没有通过跟sliding window的联想来得到这个答案; 当然, 也可能是人家对于sliding window的掌握早就炉火纯青, 以至于进行一个小的variant很自然轻松;

下面一个问题:

@ldthu said in 11-line simple Java solution, O(n) with explanation:

Hi, can you explain this line please:
j = Math.max(j,map.get(s.charAt(i))+1);
I cannot figure why you need to move this pointer (j) to either j or to the position of the last found repeating character.
Many thanks!

这个我还真没注意, 仔细回去看了一下, editorial的答案里面也有这个max操作; 但是实际上这个不难理解, 这是由于他这里的这个Map的维护方式造成的, 假如一个char的所有的occurrence都不在window内了, 但是他的信息还是有可能继续存在于这个Map里面, 这个时候你在后面的计算过程当中就有可能受其干扰; 这里这个max就是用来排除这个干扰;

这个评论也适用于我的做法:

@Ximin.Z said in 11-line simple Java solution, O(n) with explanation:

Beautiful!
This is easier than mine. I didn't use hashmap but instead using set by adding and erasing, it's so useful to keep the index of the last found, otherwise, I need to move left pointer until meet the same character, that's what costs me. Thanks!

另一个有趣的写法:

@noobsky said in 11-line simple Java solution, O(n) with explanation:

Share my concise AC java code. The way is to use a hashmap assisted with two pointers. The code is given below: 

public int lengthOfLongestSubstring(String s) {  
        int[] map = new int[256];  
        int begin = 0, end = 0, counter = 0, d = 0;  

        while (end < s.length()) {  
            // > 0 means repeating character  
            if (map[s.charAt(end++)]++ > 0) counter++;  
            while (counter > 0) if (map[s.charAt(begin++)]-- > 1) counter--;  
            d = Math.max(d, end - begin);  
        }  

        return d;  
    }

另外一个类似的解法:

@jeantimex said in Share my Java solution using HashSet:

The idea is use a hash set to track the longest substring without repeating characters so far, use a fast pointer j to see if character j is in the hash set or not, if not, great, add it to the hash set, move j forward and update the max length, otherwise, delete from the head by using a slow pointer i until we can put character j to the hash set. 

    public int lengthOfLongestSubstring(String s) {  
        int i = 0, j = 0, max = 0;  
        Set<Character> set = new HashSet<>();  

        while (j < s.length()) {  
            if (!set.contains(s.charAt(j))) {  
                set.add(s.charAt(j++));  
                max = Math.max(max, set.size());  
            } else {  
                set.remove(s.charAt(i++));  
            }  
        }  

        return max;  
    }

看了他的解释之后, 我发现我之前看editorial的时候其实没有认真考虑清楚, 他这里当出现duplicate的时候, 一个iteration其实只对i进行了一次++; 他的这个做法是因为他用的是一个conditional advance的方式来写循环, 这个我也不陌生了; 能完成这个操作的一个关键是因为set.contains的查找功能;

submission基本是波动;

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

Difficulty:Medium
Total Accepted:420.1K
Total Submissions:1.7M
Contributor:LeetCode
Companies
amazonbloombergyelpadobe
Related Topics
hash tabletwo pointersstring
Similar Questions
Longest Substring with At Most Two Distinct Characters

results matching ""

    No results matching ""