# leetcode 3 Longest Substring Without Repeating Characters最长无重复子串

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.

pos[s[0~2]] = -1，亦即将"ab""移出当前串"，同时当前长度减去3

int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}

/**
* Solution (DP, O(n)):
*
* Assume L[i] = s[m...i], denotes the longest substring without repeating
* characters that ends up at s[i], and we keep a hashmap for every
* characters between m ... i, while storing <character, index> in the
* hashmap.
* We know that each character will appear only once.
* Then to find s[i+1]:
* 1) if s[i+1] does not appear in hashmap
*    we can just add s[i+1] to hash map. and L[i+1] = s[m...i+1]
* 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k
*    let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update
*    entry in hashmap to mark the latest occurency of s[i+1].
*
* Since we scan the string for only once, and the 'm' will also move from
* beginning to end for at most once. Overall complexity is O(n).
*
* If characters are all in ASCII, we could use array to mimic hashmap.
*/

int lengthOfLongestSubstring(string s) {
// for ASCII char sequence, use this as a hashmap
vector<int> charIndex(256, -1);
int longest = 0, m = 0;

for (int i = 0; i < s.length(); i++) {
m = max(charIndex[s[i]] + 1, m);    // automatically takes care of -1 case
charIndex[s[i]] = i;
longest = max(longest, i - m + 1);
}

return longest;
}


class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}

for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)

usedChar[s[i]] = i

return maxLength

// testlongsetString.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include<iostream>

using namespace std;

void GetMaxUnRepeatSubStr(char *str)
{
//global var
int hashTable[256] ={0};
char* pMS = str;
int mLen = 0;

//temp var
char* pStart = pMS;
int len = mLen;
char* p = pStart;
while(*p != '\0')
{
if(hashTable[*p] == 1)
{
if(len > mLen)
{
pMS = pStart;
mLen = len;
}

while(*pStart != *p)
{
hashTable[*pStart] = 0;
pStart++;
len--;
}
pStart++;
}
else
{
hashTable[*p] = 1;
len++;
}
p++;
}
// check the last time
if(len > mLen)
{
pMS = pStart;
mLen = len;
}
//print the longest substring
while(mLen>0)
{
cout<<*pMS<<" ";
mLen--;
pMS++;
}
cout<<endl;
}

int main()
{
char* str1="bdabcdcf";
GetMaxUnRepeatSubStr(str1);
char* str2="abcdefb";
GetMaxUnRepeatSubStr(str2);
char* str3="abcbef";
GetMaxUnRepeatSubStr(str3);

return 0;
}

|
10月前
Leetcode 516. Longest Palindromic Subsequence

38 0
|
10月前
|
Java
Leetcode 3. Longest Substring Without Repeating Characters

41 3
|

LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
117 0
LeetCode 424. Longest Repeating Character Replacem

97 0
LeetCode 409. Longest Palindrome

67 0
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III

39 6
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构

34 4
|
1月前
|

【Leetcode刷题Python】牛客. 数组中未出现的最小正整数

68 2
|
1月前
|

【Leetcode刷题Python】从列表list中创建一颗二叉树

34 7
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈

17 4