[LeetCode] 3. Longest Substring Without Repeating Characters

PADO·2021년 1월 8일

leetcode 알고리즘

알고리즘

목록 보기

6/15

3. Longest Substring Without Repeating Characters

문제 링크: https://leetcode.com/problems/longest-substring-without-repeating-characters/

주어진 문자열에서 문자가 중복되지 않는 최대 길이 문자열의 길이를 반환하는 문제이다.

Solution

1. Bruteforce

Bruteforce 방법부터 시작하자면, 당연히 주어진 문자열로 만들 수 있는 모든 substring에 대해 Repeating Characters가 있는지 검사해야 한다.

Algorithm

모든 substring을 check하기 위해 for loop 두 개를 사용하여, 바깥 loop의 i는 0부터 n-1(n은 문자열의 길이)까지, 안쪽 loop의 j는 i+1부터 n까지 순회하도록 한다.
이 때, 사실 만들 수 있는 모든 문자열에 대해 check하려면 길이가 1인 문자열도 포함해야 하므로 j는 i+1부터 시작할 건지, i부터 시작할 건지 고민을 해야 한다.
ex) testcase가 bbbbb인 경우, longest substring without repeating characters는 길이가 1이므로 j를 i부터 순회 시킨다.
만든 substring에 대해 중복된 문자가 존재하는지 검사한다.
문자 중복 체크엔 HashSet을 사용할 수 있다.
→ 중복된 문자가 존재하지 않는다면, maxLength를 갱신한다.

구현

class Solution {
    public int lengthOfLongestSubstring(String s) { 
        if(s.length() <= 1) return s.length();
        
        int maxLength=0;
        for(int i=0; i<s.length()-1; i++) {
            for(int j=i; j<s.length(); j++) {
                if(allUnique(s, i, j)) maxLength = Math.max(maxLength, j-i+1);
            }
        }
        return maxLength;
    }
    
    boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        
        for(int i=start; i<=end; i++) {
            if(set.contains(s.charAt(i))) return false;
            set.add(s.charAt(i));
        }
        return true;
    }
}

O(n^3)의 시간복잡도로 만들 수 있는 모든 문자열을 check하고 있으므로 결과는 TLE 다.

1-1. Bruteforce Optimized

이전의 풀이에선 만들 수 있는 모든 문자열에 대해 체크했고, 모든 문자열에 대해 HashSet을 생성하여 문자열의 처음부터 끝까지 검사했다. 이 부분을 optimize 할 수 있다.

Algorithm

생성 가능한 모든 문자열을 check
→ 중복이 발생하면 이미 중복이 발생한 문자열이므로 j loop를 break
모든 문자열에 대해 HashSet을 생성하여 문자열의 처음부터 끝까지 검사한다.
→ 이미 중복된 문자가 없다고 검사된 문자열에 대해 또 다시 중복을 수행할 필요가 없다.
Set에 넣은 문자들이 다음 문자열을 검사할 때 초기화되지 않도록, Set을 전역으로 관리한다.

구현

class Solution {
    Set<Character> set = new HashSet<>();
    public int lengthOfLongestSubstring(String s) { 
        if(s.length() <= 1) return s.length();
        
        int maxLength=0;
        for(int i=0; i<s.length()-1; i++) {
            set.add(s.charAt(i));
            for(int j=i; j<s.length(); j++) {
                if(j!=i && set.contains(s.charAt(j))) break;
                maxLength = Math.max(maxLength, j-i+1);
                set.add(s.charAt(j));
            }
            set.clear();
        }
        return maxLength;
    }
}

2. Sliding Window

구현

class Solution {
    public int lengthOfLongestSubstring(String s) { 
        if(s.length() <= 1) return s.length();
        Set<Character> set = new HashSet<>();
        
        int i=0; 
        int j=0;
        int maxLength=0;
        while(i<s.length() && j<s.length()) {
            if(!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                maxLength = Math.max(maxLength, j-i);
            }
            else set.remove(s.charAt(i++));
        }
        return maxLength;
    }
}

2-1. Sliding Window Optimized

구현

class Solution {
	public int lengthOfLongestSubstring(String s) {
              int maxLength = 0;
              Map<Character, Integer> map = new HashMap<>();
              int slow = 0;
              int fast = 0;
              while(fast < s.length()) {
                  char c = s.charAt(fast);
                  if(map.containsKey(c)) {
                          slow = Math.max(map.get(c)+1, slow);
                  }
                  map.put(c, fast);
                  fast++;
                  maxLength = Math.max(maxLength, fast-slow);
              }
              return maxLength;
        }
}