Longest Substring Without Repeating Characters

Leave a comment

November 20, 2016 by oneOokay

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.


两种方法:

  • HashMap 双指针类似. (事实上也是一个一维dp了)
  • HashSet 双指针类似

HashMap类似于双指针:O(n)

  • 一个start来表示当前最长的符合条件的string的起始index
  • i用来扫描整个string。
  • HashMap<Character, Integer>:用来存character和它的index。

难点在于start值:在发现了一个重复的char之后,start值应该取(start, i – map.get(c) + 1)中的较大值。因为:

HashMap没有移除start之前的char,HashMap里面实际上是存了所有的不同的char和他们的index的。所以start的值同时也表示start 之前的index都已经扫过了,不能再取。这也表明了start只能往后移,不能往前移。

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

HashSet:

  • 用一个set来存当前的符合条件的sub string
  • start标记头
  • end标记尾,end从头扫到尾
  • 当s.charAt(end)不存在set里面,加入set,max取当前max和set.size() 较大值
  • 当s.charAt(end)存在set中的时候,开始从start起,移除char,一直到s.charAt(end)能够加进去为止(其实也就是start移到s.charAt(end)的重复的char之后)这里就是相当与前面的那个start = Math.max(start, map.get(s.charAt(i)) + 1);
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        Set set = new HashSet();
        int start = 0;
        int end = 0;
        int max = 0;
        while (end < s.length()){
            if (!set.contains(s.charAt(end))){
                set.add(s.charAt(end));
                end ++;
                max = Math.max(max, set.size());
            }else {
                set.remove(s.charAt(start));
                start ++;
            }
        }
        return max;
    }
}

dp

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

%d bloggers like this: