Longest Substring Without Repeating Characters

문제 위치

해당 문제는 문자열 s를 받고, 반복되지 않는 가장 긴 문자열을 찾는 것이다.

접근론은 아래와 같다.

HashSet을 이용한다. HashSet은 중복 요소를 허용하지 않는 데이터 구조이다.

Iterator를 2개 이용하여 문제를 해결한다.
i는 첫번째 문자 위치
j는 마지막 문자 위치이다.

첫번째 문자부터 hashset에 저장하며, 그 이후 hashset에 존재하지 않으면 계속 더하고 값이 존재하면 해당 값을 제거한다.

코드는 아래와 같다

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int s_length = s.length();
        int max_length = 0;

        HashSet<Character> set = new HashSet<>();
        
        int i=0, j=0;

        while( j < s_length ){
            if( !set.contains(s.charAt(j))){
                // hashset에 존재하지 않으면,
                set.add(s.charAt(j));
                max_length = Math.max(max_length, j - i + 1); // 이때까지 기록된 max_length v.s. 현재 찾은 문자열 길이
                j++;
            }
            else {
                // hashset에 존재하면,
                set.remove(s.charAt(i));
                i++;
            }
        }

        return max_length;
    }
}