[ LeetCode ][JAVA][3] Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

문제

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.

접근

연속된 substring에 대해서 문제를 해결해야 하므로 투포인터가 떠올랐고,

포인터를 두개 두어서 중복되는 알파벳이 들어올 때마다 새롭게 체크하는 식으로 풀었다.

중복은 Set을 이용해서 판별했다.

코드

import java.util.*;
public class LC3_LongestSubstringWithoutRepeatingCharacters {
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int len = s.length();
            if (len == 0) return 0;

            Set<Character> set = new HashSet<>();
            int lo = 0, hi = 0;
            int answer = 0;
            while (hi < len) {
                if (set.contains(s.charAt(hi))) {
                    set.remove(s.charAt(lo++));
                } else {
                    set.add(s.charAt(hi++));
                    answer = Math.max(answer, set.size());
                }
            }
            return answer;
        }
    }
}