3. Longest Substring Without Repeating Characters

Posted on | In | 浏览 次
Words count in article: 409 | Reading time ≈ 1

题目

  • Given a string, find the length of the longest substring without repeating characters.
  • Example 
    1
    2
    3
    4
    Input: "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3. 
    Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

    解题思路

  • 本题目的是得到字符串里面没有重复字符的最长子串的长度，一开始首先想到的就是两个嵌套的循环，通过暴力破解，寻找每个字符开头的最大字串，时间复杂度比较高，为O(n^2)。
  • 通过与别人讨论得到一定的启发，从头开始遍历字符，类似滑窗思想来解决本题
    • 利用一个数组来判断字符是否已经在子串中，其中字符的ASCII值作为数组的下标，其在字符串中的下标则存储在数组相应下标指向的位置
    • 假设当遇到一个字符‘a’已经出现当前子串中，则从该子串中的’a’的前一个字符继续当前子串的扩展，新的子串的初始长度为i[第二个'a'的下标]-重复字符的下标[第一个'a'的下标]
    • 时间复杂度 O(n)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lengthOfLongestSubstring(string s) {
    int maxLength = 0;  // 记录最长字串的长度
    int tmp = 0;        // 遍历字符串时候记录当前字串的长度
    int array[128];
    memset(array, -1, sizeof(int) * 128);
    for(int i = 0; i < s.length(); ++i) {
        if(array[s[i]] == -1) 
            ++tmp;
        else {
            for(int j = 0;j < 128; ++j)
                if(array[j] < array[s[i]])
                    array[j] = -1;
            tmp = i - array[s[i]];
        }
        maxLength = maxLength > tmp ? maxLength : tmp;
        array[s[i]] = i;
    }
    return maxLength;
}