# 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.

```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;
}```

http://bbs.csdn.net/topics/310174805

http://www.cnblogs.com/luxiaoxun/archive/2012/10/02/2710471.html

http://dsqiu.iteye.com/blog/1701324

http://www.ahathinking.com/archives/123.html

0 条评论

• ### 【编程练习】poj1068

Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in...

• ### leetcode 204题求素数个数

Count the number of prime numbers less than a non-negative number, n

• ### leetcode 5 Longest Palindromic Substring--最长回文字符串

Given a string S, find the longest palindromic substring in S. You may assume th...

• ### 图论--差分约束--POJ 1201 Intervals

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. ...

• ### 前缀和的应用，从一道网易笔试题说起

8月3号参加了网易提前批的笔试，笔试时间 120 分钟，然后有 10 道选择题（20分）， 4 道编程题（80分）， 2 道主观题（20分）。可以说你编程题凉了...

• ### C++ Hash表模板

利用C++类模板实现任意类型的Hash表，提供的功能有： （1）指定shmkey或内存地址创建Hash表； （2）获取指定key元素； （3）遍历指...

• ### C++核心准则ES.106:不要试图通过使用无符号类型避免负值

Choosing unsigned implies many changes to the usual behavior of integers, includ...

• ### LeetCode 1390. 四因数

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/four-divisors 著作权归领扣网络所有。商...

• ### Infinite Fraction Path

**Infinite Fraction Path** Time Limit: 6000/3000 MS (Java/Others) Memory Limit: ...