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