导航
导航

Leetcode-3. Longest Substring Without Repeating Characters

2017.02.27 尤淇  热度 ℃

题目

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.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int lengthOfLongestSubstring(String s) {

	if(s.length() < 1){
		return 0;
	}

    int start = 0;

    char[] chArr = s.toCharArray();

    int max = start + 1;
    Map<Character, Integer> map = new HashMap<>();

    for (int i = 0; i < chArr.length; i++) {
        if (map.containsKey(chArr[i])) {
            int pre = map.get(chArr[i]);

            if (pre < start) {
                map.put(chArr[i], i);
            }else{
                start = map.get(chArr[i]) + 1;
            }
        }

        if (max < i - start + 1) {
            max = i - start + 1;
        }

        map.put(chArr[i], i);

    }

    return max;
}

代码优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//根据答案优化的代码，这个代码比上面的代码简洁很多，要多学习
public int lengthOfLongestSubstring(String s) {
    if(s.length() < 1){
        return 0;
    }

    char[] chArr = s.toCharArray();

    int max = 0;
    Map<Character, Integer> map = new HashMap<>();

    for (int i = 0, j = 0; i < chArr.length; i++) {
        if (map.containsKey(chArr[i])) {
            j = Math.max(j, map.get(chArr[i]) + 1);
        }

        max = Math.max(max, i - j + 1);

        map.put(chArr[i], i);
    }

    return max;
}

总结

  • 该解法利用了HashMap的空间使得算法时间复杂度为O(n)；
  • map中的字符即为最长子串。