LeetCode 3 - Longest Substring Without Repeating Characters

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

 

문자열 s가 주어졌을 때 반복되는 문자가 등장하지 않는 가장 긴 substring을 반환하라.

 

무선 문자의 등장 여부를 관리할 필요가 있겠다. 이는 Set을 통해 관리하면 1개만 등장하는지 여부를 빠르게 판단할 수 있을 것 같다.

이제는 substring을 판단해야 한다. 이는 슬라이딩 윈도를 통해 판단하겠다.

이 슬라이딩 윈도우를윈도를 확장하다 더 이상 확장할 수 없을 때 즉, 중복 단어가 등장했을 때 기존에 해당 단어가 위치했던 곳 다음을 시작점으로 다시 윈도를 확장한다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;

        Set<Character> charSet = new HashSet<>();
        int left = 0;
        int maxLength = Integer.MIN_VALUE;

        for (int right = 0; right < s.length(); right++) {
            while (charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }

            charSet.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}