Longest Substring Without Repeating Characters (Medium)

Description

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.

Analysis

我们可以用cnt[i]来表示i字符最近出现的位置在cnt[i]
则一旦发现cnt[s[i]]!=0,那么新的长度为上一层的长度+1,和i-cnt[s[i]]+1比较中最小的。
每次更新max即可

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//C
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
int lengthOfLongestSubstring(char *s) {
    int cnt[270]={0},maxx=0,num=0;
    int i;
    for(i = 0;s[i];i++){
        if(cnt[s[i]])
            num = min(num+1,i+1-cnt[s[i]]);
        else
            num++;
        maxx = max(maxx,num);
        cnt[s[i]]=i+1;
    }
    return maxx;
}