[leetcode] Longest Substring Without Repeating Characters

 1 /*
 2   * Use two points, pBeg and pEnd, pointing to the begin and end
 3   * of current substring without repeating respectively. Integer
 4   * Array pos[256] records the last occurrence position of each
 5   * ASCII character.
 6   *
 7   * For each loop, pEnd moved forward one character. If the new
 8   * character(i.e. str[pEnd], referred as newChar) has appeared
 9   * in current substring before, move pBeg to pos[newChar]+1,
10   * and update pos[], len, etc.
11   *
12   * @author: HZT
13   * @date: 2013-3-7
14   *
15   */
16  
17  #include <iostream>
18  #include <memory>
19  #include <cstring>
20  using namespace std;
21  
22  int substring(string str){
23      int strLen = str.length();
24      if(strLen == 0) return 0;
25      
26      int maxLen = 1;
27  
28      int len = 1;
29      int beg = 0, end = 0;
30  
31      int pos[256];
32      memset(pos, -1, sizeof(pos));
33      pos[str[0]-'\0'] = 0;
34  
35      while(true){
36          end++;
37          if(end >= strLen) break;
38  
39          int lastPos = pos[str[end]-'\0'];
40          if(lastPos == -1){
41              len++;
42              lastPos = end;
43              pos[str[end]-'\0'] = end;
44          }
45          else{
46              len -= (lastPos - beg);
47              for(int i=beg; i<=lastPos; i++){
48                  if(pos[str[i]-'\0'] == i)
49                      pos[str[i]-'\0'] = -1;
50              }
51              pos[str[end]-'\0'] = end;
52              beg = lastPos + 1;
53          }
54  
55          if(len > maxLen){
56              maxLen = len;
57          }
58      }
59  
60      return maxLen;
61  }
62  
63  
64  int main(){
65      string str = "bbbbb";
66  
67      cout << substring(str) << endl;
68  
69      return 0;
70  }