LeetCode 3. Longest Substring Without Repeating Characters (Java)

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

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

Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: “pwwkew”
Output: 3
Explanation: 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.

This is a resizable sliding window problem. We can use char array to make the window (+1 in the window, -1 out of the window). We move right to enlarge the window, whenever repeat characters occur we save it to a hashmap. And until repeat characters exist, we move left to shrink the window. When repeat characters disappear, we compare the string of the window with the shortest string before.

This is the code:

Download code: https://github.com/tinyfool/leetcode/tree/master/src/p0003

Want to know details of the sliding window algorithm, check my post: The Sliding Window Algorithm for string and array.

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.