首页 > 技术文章 > Longest Substring Without Repeating Characters

YaolongLin 2015-10-02 01:44 原文

 

题目:

  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.

 

思路:

  用两个游标遍历字符串,后一个游标每读取一个字符将其记录在标志数组 record 中,若 record 已经存在这个字符,则存下当前两个游标之间的距离,前一个游标后移直到当前字符与后一个游标所指字符相同为止,当后一个游标遍历完字符串即可得到最长无重复串。

 

代码:

 1 int lengthOfLongestSubstring(char* s) {
 2     int record[128] = {0};
 3     int start, end, length = 0;
 4     if (s[0] == '\0')    return 0;
 5     if (s[1] == '\0')    return 1;
 6     for (start = end = 0; s[end] != '\0'; ++end){
 7         if (record[s[end]] == 0)    record[s[end]] = 1;
 8         else {
 9             if (length < end - start)
10                 length = end - start;
11             while (s[start] != s[end])
12                 record[s[start++]] = 0;
13             ++start;
14         }
15     }
16     if (length < end - start)
17         length = end - start;
18     return length;
19 }
Longest Substring Without Repeating Characters

 

推荐阅读