[LeetCode] 3. Longest Substring Without Repeating Characters

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

개요

1. 문자열 s가 주어진다.
2. 하위 문자열이 반복되지 않는 substring 의 최대 길이를 찾아라.
   • substring 에는 동일한 문자가 있어서는 안된다.

문제 해결 아이디어

• 케이스 살펴보기
  • 문자열이 "pww" 인 경우
    • 구간 [0:0] 내에 동일한 문자가 없다.
      ➡️ 따라서 구간을 오른쪽 한 칸 이동한다.
      
    • 구간 [0:1] 내에 동일한 문자가 없다.
      ➡️ 따라서 구간을 오른쪽 한 칸 이동한다.
      
    • 구간 [0:2] 내에 동일한 문자가 있다.
      ➡️ 따라서 구간을 첫번째 동일한 문자인 인덱스 1 다음 칸으로 이동한다.
      

• 특정 조건을 만족하는 구간 (subString) 을 찾아야 한다.
  • 여기서는 문자의 반복이 없는 구간
  • 연속적인 데이터의 하위 집합을 찾아야 함
• 구간의 크기가 최대가 되도록 해야 한다.
  • 구간의 크기가 가변적인 경우

🧐 슬라이딩 윈도우를 활용하자

의사 코드

1. 왼쪽 인덱스와 오른쪽 인덱스를 가르키는 포인터를 선언한다.
2. (왼쪽 인덱스 : 오른쪽 인덱스) 구간 내 동일 문자가 있는지 검사한다.
3. 구간 내 동일 문자가 있다 (조건)
   3-1. 왼쪽 인덱스 = 처음 나오는 동일 문자 다음 인덱스
4. 구간 내 동일 문자가 없다 (조건)
   4-1. 구간 길이가 최대인가 (조건)
   4-1-1. max 값을 업데이트한다.
   4-2. 오른쪽 인덱스를 이동한다.

left = 0
right = 1
while(right < 문자열 길이){
	for(i=left to right){
    	do [left:right] 구간 내 문자열[i]와 동일 문자있는지 검사
        if(동일 문자 있다){
        	break
        } 
    }
    
    if([left:right] 구간 내 중복있음) {
    	left = i + 1;
    } else {
    	if(right - left > max){
        	max = right - left
        }
    }
}
return max

결과

전체 코드 github 링크

다른 풀이

public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet();
        int max = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            while(!set.add(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

set.add() 는 값이 존재할 경우 false , 값이 없을 경우 true를 반환한다.

문자열 "pwwke" 를 예를 들면,

1. right=0 'p'는 set에 바로 들어갈 수 있다.
2. right=1 'w'는 set에 바로 들어갈 수 있다.
3. right=2 'w'는 set에 바로 들어가지 못한다.
   1. set에서 'p'를 제거한다. 왼쪽 인덱스를 증가시킨다.
   2. set에서 'w'를 제거한다. 왼쪽 인덱스를 증가시킨다.
   3. 'w'는 set에 들어갈 수 있다.
      ➡️ 결과적으로 right 과 left 인덱스 'w'를 가르키게 되었다.
4. right=3 'k'는 set에 바로 들어갈 수 있다.
5. right=4 'e'는 set에 바로 들어갈 수 있다.

.

나는 indexOf 을 활용해 동일한 문자가 있는지 체크하고, 동일한 문자의 인덱스 다음으로 왼쪽 인덱스를 옮긴다. 그래서 시간복잡도가 굉장히 크게 나와서 아쉬웠다.

그런데 Set 자료구조를 통해 왼쪽 인덱스가 어느정도 이동하면 되는지 간단하게 카운트 할 수 있었다. 구간 내 동일한 문자가 있으면 구간이 수정되기 때문에, 결국에는 동일한 문자가 구간에 최대 두 개 밖에 있을 수 없다. 이 점을 토대로 문자가 구간 내 나왔었는지 체크하는데 Set을 활용했으면 좋았을 것 같다.