leetcode top interview 150 | Longest Substring Without Repeating Characters | Sliding window

 

Question

 

주어진 문자열 s에서 반복되는 문자가 없는 하위문자열의 최대 길이를 리턴 

 

Accepted Code - O(N^2)

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        Set<Character> set = new HashSet<>();// set으로 문자열 중복을 체크
        
        for(int left = 0; left<s.length(); left++){
            set.add(s.charAt(left));
            int len = 1;
            maxLen = Math.max(len, maxLen);
            
            for(int right = left + 1; right<s.length(); right++){
                char c = s.charAt(right);
                if(set.contains(c)) break;
                set.add(c);
                len++;
                maxLen = Math.max(len, maxLen);
            }
            
            set.clear();
        }

        return maxLen;       
    }
}

문자의 중복체크를 위해 set 자료구조를 사용했고 left를 0부터, right를 left+1부터 증가시켜가며 maxLen을 계속해서 갱신했다. 

left위치를 증가시키면 set자료구조를 clear하고 다시 넣어야 한다고 생각했었는데, 중복된 문자가 없는 경우에도 clear시키는 것은 불필요하다.

 

Accepted Code - Sliding Window

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        Set<Character> set = new HashSet<>();
        
        for(int left = 0, right = 0; right<s.length(); right++){
            char c = s.charAt(right);
            while(set.contains(c)){
                set.remove(s.charAt(left));
                left++;
            }
            set.add(c);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;       
    }
}

 

Solve

 

set에 문자를 넣다가 중복된 문자가 발생하면 넣기 시작한 인덱스부터 순차적으로 중복여부를 확인하며 중복문자를 제거하면 된다고 생각했다.

set은 순서가 없이 저장되는 자료구조이기 때문에 연속된 문자열의 길이를 저장하기 위해서는 시작인덱스와 순차적으로 증가할 인덱스 두개가 필요하다. maxLen갱신도 중복을 제거한 연속된 문자로 구성되어있을때만 길이를 갱신하면 된다.

따라서 슬라이딩 윈도우 접근방식을 활용하였고, O(N)의 복잡도로 개선하였다. 

 

Sliding Window : 슬라이딩 윈도우
연속된 데이터에서 일정한 크기의 구간을 움직이며 문제를 해결하는 패턴으로, 연속적인 해당 패턴의 하위집합을 찾는데 활용된다

 

left포인터와 right포인터를 동일한 위치에서 출발시키고, right포인터를 증가시켜가며 중복여부를 체크한다.

중복이 발생하면 left 포인터를 증가시키면서 set에 있는 문자를 제거하고, 중복되지 않는 문자만 가진 연속된 문자들로 구성될 수 있도록 한다. 중복되지 않은 연속된 문자열로 구성되어있을때 right 인덱스에서 left 인덱스를 뺀 길이를 answer에 갱신한다.

 

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150 

Longest Substring Without Repeating Characters - LeetCode