[Leetcode Top Interview 150] 3. Longest Substring Without Repeating Characters

난이도 : medium

 

문제링크

• 반복되는 문자 없이 가장 긴 substring의 길이를 구하라
• 0 <= s.length <= 5 *10^4
• s는 알파벳, 정수, 공백으로 이루어짐

 

1. 접근법

• substring은 연속된 원소들
• 가장 긴 길이를 구하기 위해서는 배열의 모든 원소를 순회해야 한다
• 슬라이딩 윈도우 패턴을 사용하여
  • 유일한 원소들로 구성된 substring의 크기를 전부 비교
  • 제일 긴 길이를 리턴

 

2. 의사코드

for (right 는 1부터 전체길이까지) {
	for (i는 left부터 right-1까지) {
    	if (s[i] == s[right]) {
        	left는 i+1
        } 
    }
    
    ans는 max(ans, right-left)
}

return ans

 

3. 구현 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans=0;                
        int left = 0;   

        if (s.length() == 0) {
            return ans;
        }

        for (int right = 1; right < s.length(); right++) {                        
            for (int i = left; i < right; i++) {
                if (s.charAt(i) == s.charAt(right)) {
                    left = i+1;    
                    break;
                }               
            }

            if (ans < right - left) {
                ans = right - left;    
            }
        }
                        
        return ans+1;
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n^2) - n번 n개의 원소를 반복하므로
• 공간복잡도 : O(1) - n개 원소를 돌아도 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘

 

5. 개선점

모르겠다 생각이 나질 않는다

 

6. 회고

시간복잡도를 줄일 수 있지 않을까 생각이 들었지만 이것도 간신히 푼거라 찾아보았다

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0;
        int j = 0;
        int max = 0;

        Set<Character> hashSet = new HashSet<>();

        while (j < s.length()) {
            if (!hashSet.contains(s.charAt(j))) {
                hashSet.add(s.charAt(j));
                j++;
                max = Math.max(max, hashSet.size());
            } else {
                hashSet.remove(s.charAt(i));
                i++;
            }
        }
        
        return max;
    }
}

(출처: NickWhite youtube) 

• substring은 반복이 허용되지 않으므로 각 요소들을 hashset에 캐싱한다
• sliding window를 늘려가면서
  • out pointer의 char값이 hashSet에 없다면
    • hashSet : out pointer값 추가
    • out pointer++
    • max값 갱신 (기존 max와 hashSet의 size 비교)
  • out pointer의 char값이 hashSet에 있다면
    • hashSet : int pointer값 삭제
    • int pointer++;

 

(메모) 시간복잡도를 줄이기 위해 캐싱에 사용할 자료구조를 쓸 것

(메모) 반복허용이 불가한 데이터에 대해 set을 사용할 것