LeetCode - 3. Longest Substring Without Repeating Characters(Hash Table, String, Sliding Window)*

문제

문자열 s가 주어지면, 반복되는 문자 없이 가장 긴 부분 문자열의 길이를 구한다.

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

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.

풀이

자바입니다.

• HashSet과 Sliding Window를 사용했습니다.
• 이 풀이는 조건을 만족했을 때 오른쪽창이 오른쪽으로 이동하며 열리고(right++), 왼쪽창은 오른쪽으로 이동하며 닫힙니다(left++).
• constais() 를 사용해서 글자가 있으면(중복되는 글자 발견) left의 글자를 제거.
• 없으면 right의 글자를 추가.

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

ex) s="pwwkew"; 시각화