• 23.9%

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, 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.

leetcode 3

leetcode 76

leetcode 159

code 1：

https://discuss.leetcode.com/topic/4083/shortest-o-n-dp-solution-with-explanations

Shortest O(n) DP solution with explanations

code 2：

start 表示最长字符串起始的位置。

i表示终止的位置，或者说当前到达的位置。

https://discuss.leetcode.com/topic/30941/here-is-a-10-line-template-that-can-solve-most-substring-problems

I will first give the solution then show you the magic template.

The code of solving this problem is below. It might be the shortest among all solutions provided in Discuss.

1. Minimum Window Substring

Here comes the template.

For most substring problem, we are given a string and need to find a substring of it which satisfy some restrictions. A general way is to use a hashmap assisted with two pointers. The template is given below.

One thing needs to be mentioned is that when asked to find maximum substring, we should update maximum after the inner while loop to guarantee that the substring is valid. On the other hand, when asked to find minimum substring, we should update minimum inside the inner while loop.

The code of solving Longest Substring with At Most Two Distinct Characters is below:

The code of solving Longest Substring Without Repeating Characters is below:

Update 01.04.2016, thanks @weiyi3 for advise.

I think this post deserves some upvotes! : )

https://discuss.leetcode.com/topic/24739/c-code-in-9-lines

16ms, 62.39%, 23 July 2016

https://discuss.leetcode.com/topic/1914/my-o-n-solution

My O(n) Solution

if only use DP, it’s an O(n*n) solution, adding a map to get O(n).

#### python

https://discuss.leetcode.com/topic/11632/a-python-solution-85ms-o-n

104ms, 84.17%, 23 July 2016

#### java

https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation

11-line simple Java solution, O(n) with explanation

the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.

https://discuss.leetcode.com/topic/25499/share-my-java-solution-using-hashset

Share my Java solution using HashSet

The idea is use a hash set to track the longest substring without repeating characters so far, use a fast pointer j to see if character j is in the hash set or not, if not, great, add it to the hash set, move j forward and update the max length, otherwise, delete from the head by using a slow pointer i until we can put character j to the hash set.

https://leetcode.com/articles/longest-substring-without-repeating-characters/

22ms, 31.97%, 23 July 2016

The previous implements all have no assumption on the charset of the string s.

If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.

Commonly used tables are: