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

思路: 求不重复的最大子串的长度, 我们可以用一个hashset来作一个lookup记录存的substring。 我们用一个指针start来记录子串的起始位置。 然后遍历给定字符串的每个字符,判断是否在hashset中存过。如果lookup没有存过,就存进去;如果存过,说明遇上duplicate了,之前存的子串都要remove掉,我们可以用个临时变量j=start来获得之前存进去的子串的起始位置,然后挨个移除掉,最后更新下start=j+1. 继续往下面找, 因为是要求最长的子串,我们可以用一个maxLen的全局变量在每次循环完了跟i-start+1比较下,最后返回maxLen即可.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        HashSet lookup = new HashSet();
        int start = 0; // the start index of substring 
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (lookup.contains(c)) { // found dups
                int j = start;  // back to the previous start
                while(j < s.length() && s.charAt(j) != c) {
                    lookup.remove(s.charAt(j));
                    j++;
                }
                start = j + 1; // reset start 
            } else {
                lookup.add(c);
            }
            maxLen = Math.max(maxLen, i - start + 1);
        }
        return maxLen;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s