[LeetCode] 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

LeetCode

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

문자열 s가 주어졌을 때, 중복되는 문자가 없는 가장 긴 부분 문자열의 길이를 구하세요.

 

Example

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

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

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.

---

1. 문제 요구사항 분석

반복되는 숫자 없이 가장 긴 문자열을 찾는 것

 

2. 접근 전략

😄 2개의 값씩 반복문을 돌면서 비교하여 왼쪽과 오른쪽의 값이 같으면 왼쪽의 값까지만 길이를 계산하고, 동일하지 않으면 그 다음 값을 비교 + 이 때 멀리 있는 값은 반복되는 값인지 확인하기 어렵기 때문에 HashSet에 넣고 길이 확인 → 시간복잡도 O(n)

 

import java.util.HashSet;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 0;
        HashSet<Character> set = new HashSet<>();
        int left = 0;

        // right 포인터는 0부터 끝까지 1칸씩 전진합니다.
        for (int right = 0; right < s.length(); right++) {
            
            // 중복이 없어질 때까지 left를 당기면서 빼냅니다!
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            
            // 이제 중복이 확실히 없으므로 안심하고 창문에 넣습니다.
            set.add(s.charAt(right));
            
            // 최대 길이 갱신 (현재 창문의 길이는 right - left + 1)
            answer = Math.max(answer, right - left + 1);
        }

        return answer;
    }
}