Medium Two Pointers

Adobe

Alation

Amazon

Apple

Bloomberg

ByteDance

Coupang

Expedia

Facebook

Goldman Sachs

Google

Microsoft

More

Oracle

SAP

Splunk

Spotify

Uber

VMware

Yahoo

eBay

2021-01-22

3. Longest Substring Without Repeating Characters

Question:

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Solution:

Using a pointer to point to left and right which represents the high and low of the substring without any repeting character. If it was not the case, remove the left character from the hashset.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int left = 0, right = 0, result = 0;
        while (right < s.length()) {
            if (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            } else {
                set.add(s.charAt(right));
                result = Math.max(result, right - left + 1);
                right++;
            }
        }
        return result;
    }
}