Longest Substring Without Repeating Characters

Posted on   |   In   |  

计算出给定的字符串的最长无重复字串

3.Longest Substring Without Repeating Characters

题目：
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.
大致意思：给定一个字符串，求出这个字符串的最长无重复字符的字串

思路:
(1)建立哈希表，储存相应的字符在字符串中的位置；
(2)从前往后扫字符串(start指针指向扫描的前端),当字符出现过时(前一次出现的位置为index1，这一次出现的位置为index2)，就将start指针指向index + 1，在从start继续扫描(同时重置hash表，防止index1之前的元素的干扰)，

图片描述算法
图片来源(http://fisherlei.blogspot.com/2012/12/leetcode-longest-substring-without.html)

在这里需要注意的问题:
(1)字符并不限于26个字符
(2)注意处理原本字符串就不重复的情况

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0)   return 0;
        
        int chart[256];
        fill(chart, chart+256, -1);
        int start = 0;
        int max = 1;
        int len = 0;   //加入len是为了处理字符串本来就不重复的情况
        for(int i = 0; i < s.size(); i++, len++){
            if(chart[s[i]] >= 0){
                
                //比之前的字串长
                if(i - start  > max)
                    max = i - start;
                    
                //重新开始，从重复的字符串开始
                start = chart[s[i]] + 1;
                i = start;
                len = 0;
                fill(chart, chart+256, -1);
            }
            
            chart[s[i]] = i;
        }
        return max > len ? max: len;
    }
};

version 2
修改后更简洁的方法
对以上的代码进行精简，可以发现：
当遇到与以前重复的字符时(记第一次字符出现的位置为index1,第二次出现的位置为index2)那么此时start的位置变为index1 +1, 继续向后扫描，当出现重复的时候(版本1中将hash表重置了)，
(1)如果此位置在start（hash[ s[end] ] >=
start）以前，则直接计算(end -start +1)
(2)此字符还没有加入到hash表中，计算出以这个字符结尾的字串(没有重复的字符串)，比较长度
(3)此字符前一次出现的位置在start 以后，则更新start的位置，计算长度

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
int lengthOfLongestSubstring(char* s) {
    int hash[256];
    memset(hash, -1, sizeof(hash));
    
    int length = strlen(s);
    if(length == 0)
        return 0;
    
    int start = 0; 
    int end = 0;
    int maxL = 1;
    
    while(end < length){
        
        /*
         *此处需要重点说明，end表示当前的字符，end以前的字符均已得到处理，
         *
        */
        if(hash[s[end]] >= start)
            start = hash[s[end]] + 1;
        
        
        maxL = (end - start + 1) > maxL ? (end - start + 1):maxL;
        hash[s[end]] = end;
        end++;
    }
    return maxL;
}

参阅文章：
(http://fisherlei.blogspot.com/2012/12/leetcode-longest-substring-without.html)
(http://blog.csdn.net/likecool21/article/details/10858799)
(http://www.acmerblog.com/leetcode-longest-substring-without-repeating-characters-5318.html)