[LeetCode] 3. Longest Substring Without Repeating Characters

■ 문제

문제

문자열 s 중 중복되지 않은 부분배열의 최대길이를 구하는 문제이다.

 

■ 풀이

처음 설계를 할 때 자료구조 사용 없이, String.substring() 을 사용하여 풀고자 했다.

1. i->끝까지 for 문 순회하면서 시작하는 첫번째 startChar 를 추출
2. startChar 인덱스를 제외하고 뒤의 문자들을 substring() 으로 서브 문자열 추출
   1. 이 과정에서 서브 문자열에 startChar 포함 여부 확인
      1. 있으면 x
      2. 없으면 최대 길이 업데이트

 

이러한 설계로 풀려고 하였으나 반례가 존재했다.

startChar 가 아닌 다른 중복되는 문자에 대한 예외처리가 필요하다.

예를 들어 "abcabcbb" 일때, c가 4번째 a가 startChar 일 경우, 뒤에 "a" 가 없기 때문에 해당 케이스는 통과하지 못한다.

 

때문에 자료구조 Set 을 사용하여 해결하는 방법을 선택했다.

이 방법이 이런 서브 문자열을 확인하는 문제에서 범용적으로 사용될 수 있을 것 같다고 생각된다.

1. Set<Character> 를 생성한다.
2. String s 를 for 문으로 처음부터 끝까지 순회한다.
   1. 이 과정에서 해당 인덱스 별로 Set 에 존재 여부를 확인
      
      1. Set에 존재 하지 않을 경우? add() 한다. + 최대 길이를 업데이트 한다.
      2. 존재 할 경우? 중복되는 문자가 존재한다는 뜻이므로, Set 데이터를 모두 지워준다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int size = s.length();
        int maxLength = 0;
        Set<Character> charSet = new HashSet<>();
        int left = 0;

        for(int right=0; right < size; right++){
            if(!charSet.contains(s.charAt(right))){
                charSet.add(s.charAt(right));
                maxLength = Math.max(maxLength, right-left + 1);
            }else{ // 중복?
                while(charSet.contains(s.charAt(right))){ // 기존꺼 left 올리면서 삭제
                    charSet.remove(s.charAt(left));
                    left++;
                }
                charSet.add(s.charAt(right));
            }
        }
        return maxLength;
    }
}

 

right 와 left 인덱스를 사용하여 부분문자열을 확인하는 방법이 핵심이다.