Monday, December 24, 2012

[LeetCode] 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.
» Solve this problem

[解题思路]

[Code]
Version 1
``````1:    int lengthOfLongestSubstring(string s) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      int count[26];
5:      if(s.size() ==0) return 0;
6:      memset(count,-1, sizeof(count));
7:      int start = 0;
8:      int maxV = 0;
9:      for(int i=0; i< s.size(); i++)
10:      {
11:        int index = s[i] - 97;
12:        if(count[index] >= 0)
13:        {
14:          if(maxV < (i -start))
15:          {
16:            maxV = i-start;
17:          }
18:          i = count[index];
19:          start = i+1;
20:          memset(count,-1, sizeof(count));
21:          continue;
22:        }
23:        count[index] = i;
24:      }
25:      if(maxV < (s.size() -start))
26:      {
27:        maxV = s.size()-start;
28:      }
29:      return maxV;
30:    }
``````

Version 2, refactor the code at 3/4/2013
``````1:       int lengthOfLongestSubstring(string s) {
2:            int count[26];
3:            memset(count, ````-1````, 26*sizeof(int));
4:            int len=0, maxL = 0;
5:            for(int i =0; i< s.size(); i++,len++)
6:            {
7:                 if(count[s[i]-'a']>=0)
8:                 {
9:                      maxL = max(len, maxL);
10:                      len =0;
11:                      i = count[s[i]-'a']+1;
12:                      memset(count, ````-1````, 26*sizeof(int));
13:                 }
14:                 count[s[i]-'a']=i;
15:            }
16:            return ````max(len, maxL)````;
17:       }
``````

Note:
1. Line 3, since we store the index in array, so initializing the array as 0 will mistake the logic.
2. Line 16, catch the last string. for example, "abcd", if no Line 16, it will just return 0 since the Line 9 won't be triggered.