3. Longest Substring Without Repeating Characters.md

3. Longest Substring Without Repeating Characters

Problem

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

tag:

Solution

最简单的方法是暴力破解，找出以每一个字母开头的最大字串， 时间复杂度为O(N²)

假设，在一次计算的过程中，字串开始位置为p,在j位置遇到重复字母b, 重复的位置为i, i<j

.a...b....b.....
 ^   ^    ^
 p   i    j

当前字串长度为len(p) = j-p, 注意到a到b之间所有字符开始的字串长度均小于len(p),因此以p与i之间字符的为起点的子串没必要计算, 从i+1位置开始继续计算。例如，abcd(b)是目前最大最长的子串,则没必要计算bcd(b)

一种优化的算法如下:

abcdbec // 从字符串的起始位置开始判断
^
...
abcdbec // 找到了重复的字母
^   ^
abcdbec // 找出当前子字符串中重复字母的位置
 ^
...
abcdaec // 从此位置的后面继续找子字符串
 ^   ^
...

实现时，可以256长度的boolean数组替代哈希表，实现字符的O(1)查找， 数组下标为对应字符的ASCII码

遍历字符串,用i纪录子串开始位置，j纪录子串结束位置，如果发现重复字符，更新i位置为重复字母位置加一, 并把i之前的字符重设为false。然后更新字串最大长度。O（2n) 时间复杂度 java

    public int lengthOfLongestSubstring(String s) {
        boolean[] exists = new boolean[256];
        int i = 0, maxLen = 0, len = s.length();
        for(int j=0; j<len; j++) {
            while(exists[s.charAt(j)]) {
                exists[s.charAt(i++)] = false;
            }
            exists[s.charAt(j)]=true;
            maxLen = Math.max(j-i+1, maxLen);
        }
        return maxLen;
    }

go

func lengthOfLongestSubstring(s string) int {
	exists := make([]bool, 256)
	i, maxLen := 0, 0
	for j, v := range s {
		for exists[v] {
			exists[s[i]] = false
			i++
		}
		exists[v] = true
		if maxLen < j-i+1 {
			maxLen = j - i + 1
		}
	}
	return maxLen
}

如果采用map存储，可做到一次遍历

    public int lengthOfLongestSubstring(String s) {
        int[] charMap = new int[256];
        Arrays.fill(charMap, -1);
        int i=0, maxLen = 0;
        for(int j=0; j<s.length(); j++) {
            if(charMap[s.charAt(j)]>=i) {
                i = charMap[s.charAt(j)]+1;
            }
            charMap[s.charAt(j)] = j;
            maxLen = Math.max(j-i+1, maxLen);
        }
        return maxLen;
    }