LeetCode 3. Longest Substring Without Repeating Characters

Description

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.

Explanation

We use two pointers technique to solve the problem. One slow pointer i, one fast pointer j.

We also add a HashSet to store the characters which have been visited by j pointer to help detect repeating characters.

We keep moving j pointer right further.

  • If current s.charAt(j) character is not in the HashSet, we add the character to the HashSet and keep moving j further.
  • If current s.charAt(j) character is in the HashSet, we remove the character i is visiting and move i forward. At this point, we found the maximum size of substrings without duplicate characters start with index i. We move pointer one step further.

When j pointer iterates all the characters of the string, we get the max length of the longest substring without repeating characters.

Video Tutorial

Java Solution

7 thoughts

  1. Hello There,
    If we consider this use-case, “abcddefghijal” – for this string, shouldn’t the output be 6 and not 9? i.e. (efghij) and not (defghijal) as d and a are repeating. Please correct me if I am wrong. Thanks.

Leave a Reply

Your email address will not be published. Required fields are marked *