「每日一道算法题」Longest Substring Witho

OJ address

OJ website : 3. Longest Substring Without Repeating Characters

Description

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

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.

Solution in C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int letter[130];

int lengthOfLongestSubstring(char* s) {
    int left, count, index, max, preIndex;
    left = count = index = max = preIndex = 0;
    memset(letter, -1, sizeof(letter));
    for (int i=0;s[i]!='\0';++i) {
        index = s[i]-'A' + 65;
        if (letter[index] == -1) {
            letter[index] = i;
            ++count;
        }
        else {
            if (count > max) max = count;
            int tmp = letter[index];
            while(left <= tmp) {
                int preIndex = s[left]-'A' + 65;
                letter[preIndex] = -1;
                ++left;
            }
            count = i - left + 1;
            letter[index] = i;
        }
    }
    return count>max?count:max;
}

int main(int argc, char const *argv[])
{
    char *ch = "abcabcbb\0";
    int t = 0;
    t = lengthOfLongestSubstring(ch);
    printf("%d\n", t);
    return 0;
}

Solution in Python

# dic 方法
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        left = 0
        maxlen = 0
        dict = {}
        for i in range(len(s)):
            dict[s[i]] = -1
        for i in range(len(s)):
            if dict[s[i]] != -1
                while left <= dict[s[i]]:
                    dict[s[left]] = -1
                    left += 1
            if i + 1 - left > maxlen:
                maxlen = i + 1 - left
            dict[s[i]] = i
        return maxlen

# set 方法
class Solution:
    def lengthOfLongestSubstring(self, s):
        left, right = 0, 0
        chars = set()
        res = 0
        while left < len(s) and right < len(s):
            if s[right] in chars:
                if s[left] in chars:
                    chars.remove(s[left])
                left += 1
            else:
                chars.add(s[right])
                right += 1
                res = max(res, len(chars))
        return res

My Idea

方法都一样，无论是set还是字典又或是数组，思路都是一样的：

1. 先声明一个int的指针指向最前面的字符
2. 遍历一遍字符串，O(n)的时间复杂度,把单个字符保存在对应的数组/set集合/字典中，若遇到相同的字符，就移动int的指针，把相同字符以及前面所有保存过的字符在数组/set集合/字典中清除掉，然后记录一下当前的子串长度。
3. 遍历到最后，然后子串长度和之前子串长度进行比较，最大的子串长度便是我们需要的结果。