Longest Substring Without Repeating Characters

Question

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.

Tags

• Hash
• Two Pointer
• String

Thought

Use a set to store the characters of the substring containing the current item in each index in the loop. Then use two pointers to traversal through the string. The pointer start represent the start index of the substring and the end pointer represent the current index in the loop.

Code

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        visited = set()
        start = end = 0
        maxLength = 0
        while end < len(s):
            if s[end] not in visited:
                visited.add(s[end])
                maxLength = max(maxLength, len(visited))
            else:
                while s[start] != s[end] and start < end:
                    visited.remove(s[start])
                    start += 1
                start += 1
                maxLength = max(maxLength, len(visited))
            end += 1
        return maxLength