Thursday, April 20, 2017

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

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.
Thoughts:
Two Pointers or take it as the sliding window, every time keep the j on the start point, keep moving i. If found the duplicate character, then move j. Record the max value.
 

Array:

Because the ASCII code a total of 256, borrow a 256-size integer array, Java if not given integer assignment, then its default value is 0, began to traverse the string from the beginning, the characters into decimal numbers as index , Then mOccur [index] plus 1, that is, the number of positions at this time is not 0. If you add 1 after the number is greater than 1, then that the characters have appeared once, once without a repeat character substring to the end here. The meaning of the j variable in this code is the starting coordinate of the longest substring without the repeat character, so when the value of mOccur [index] is greater than 1, it is necessary to move j backward. In addition, each cycle will update the maximum.

public int lengthOfLongestSubstring(String s) {
        int[] mOccur = new int[256];
        int maxL = 0;
        for(int i = 0, j = 0; i < s.length(); ++i){
            char ch = s.charAt(i);
            ++mOccur[ch];
            while(mOccur[ch] > 1){
                --mOccur[s.charAt(j++)];
            }
            maxL = Math.max(maxL, i - j + 1);
        }
        return maxL;
    }


HashMap:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        HashSet set = new HashSet();
        int leftBound = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                while (leftBound < i && s.charAt(leftBound) != s.charAt(i)) {
                    set.remove(s.charAt(leftBound));
                    leftBound++;
                }
                leftBound++;
            } else {
                set.add(s.charAt(i));
                max = Math.max(max, i - leftBound + 1);
            } 
        }

        return max;
    }
}
We use the sliding window method. We slide the leftBound if we found the duplicate character, otherwise, keep sliding the right pointer i. This method leftBound is used to represent the starting position of the longest substring without repeating characters. Keep record the max value of the subset of unique characters. Finally, you can get the max.

No comments:

Post a Comment