[LeetCode] 3. Longest Substring Without Repeating Characters - 투포인터(Two Pointer) + 완전탐색(BruteForce) JAVA

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

코드설명

투포인터(Two Pointer) + 완전탐색(BruteForce) 를 활용합니다.

 

이 문제에서 투포인터를 떠올렸다면 O(N)의 시간복잡도로 구현할 수 있습니다.

투포인터를 떠오를 수 있는 단서는 subsequence, 부분연속수열이라는 점입니다. 연속수열이기에 투포인터를 적용할 수 있습니다.

완전탐색으로 구현할경우에는, O(N^2)인데, 시간초과가 발생하지는 않습니다. 이 문제의 경우 분기되는 DFS가 없고, 한 방향으로만 작동하기에 Cache를 적용한다고해도 크게 상관없습니다.

코드

완전탐색을 활용한 코드입니다.

import java.util.*;
class Solution {
    String S;
    int[] alphabet = new int[26];
    int[] cache = new int[5 * 10*10*10*10 + 1];
    HashSet<Character> hashset = new HashSet<>();
    public int lengthOfLongestSubstring(String s) {
        S = s;
        Arrays.fill(cache, -1);
        return DFS(-1);
    }

    int DFS(int idx){
        if(idx == S.length()){
            return 0;
        }
        if(cache[idx + 1] != -1) return cache[idx + 1];
        if(idx == -1){
            int ret = 0;
            for(int i=0; i<S.length(); i++){
                Arrays.fill(cache, -1);
                hashset.add(S.charAt(i));
                ret = Math.max(ret, DFS(i));
                hashset.remove(S.charAt(i));
            }
            return ret;
        }
        int ret = 1;
        if(idx + 1 < S.length() && !hashset.contains(S.charAt(idx + 1)) ){
            hashset.add(S.charAt(idx + 1));
            ret = Math.max(ret, DFS(idx + 1) + 1);
            hashset.remove(S.charAt(idx + 1));
        }
        return cache[idx + 1] = ret;
    }
}

 

투포인터를 활용한 코드입니다.

import java.util.*;
class Solution {
    String S;
    HashSet<Character> hashset = new HashSet<>();
    public int lengthOfLongestSubstring(String s) {
        S = s;
        int left = 0, ret = 0, answer = 0;
        for(int i=0; i<S.length(); i++){
            if(hashset.contains(S.charAt(i)) == true){
                hashset.remove(S.charAt(left));
                i--;
                left++;
                answer = Math.max(answer, ret);
                ret--;
            }else{
                hashset.add(S.charAt(i));
                ret += 1;
                answer = Math.max(answer, ret);
            }
        }
        return answer;
    }
}