LeetCode 3. Longest Substring Without Repeating Characters

문제

조건

• 반드시 문자열의 순서가 보장되어야 한다.
  이미 있는 문자가 나오면 탐색을 중단해야함(★포인트)
• curr 리스트를 Set 자료형으로 선언해서 중복제거하며 담아봤는데
  그렇게 하니, 중복 요소가 나오면 pass하고 다음 요소를 집어넣게 됨
  => 다음 요소 순회가 아니라 바로 리턴해주어야 한다.

풀이 - 완전 탐색

신경 쓴 부분

• 요소 간 중복을 체크하고, 중복 발생 시 순회 중단
  - 구현은 stream().boxed().anyMatch(x->x~)을 사용

• visited배열로 방문 여부 체크

• 중복없을 시 curr리스트에 추가

• 모든 문자 요소를 start로 지정해 경우의 수 돌아야하기 때문에
  for문 내 백트래킹 호출

상세 풀이

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<ArrayList<Character>> comb = new HashSet<>();
        
        for(int i=0;i<s.length();i++){
            boolean[] visited = new boolean[s.length()];
            backtracking(s,i,comb,visited,new ArrayList<>());
        }
        System.out.println(comb);
        int max=0; 
        for(ArrayList<Character> c:comb){
            max=Math.max(max,c.size());
        }
        return max;
    }
    public void backtracking(String s,int start,Set<ArrayList<Character>> comb,boolean[] visited,ArrayList<Character> curr){
        if(curr.size()>0 && curr.size()<=s.length()){
            comb.add(new ArrayList<>(curr));
            return;
        }
        for(int i=start;i<s.length();i++){
            if(!visited[i]){
                char c = s.charAt(i);
                if(curr.size()>0){ 
                    if(!curr.stream().anyMatch(ch -> ch==c)){
                        curr.add(c);
                        visited[i]=true;
                    }else return;
                }else{
                    curr.add(c);
                    visited[i]=true;
                }
                backtracking(s,i+1,comb,visited,curr);
               
            }
            
        }

    }
}

• 문제 발생
  
  테스트 케이스 987개 중 986번에서 시간 초과가 떴다.
  장황한 테케를 보고 순간 당황..
  접근법이 틀렸구나, 생각이 들었다.
  이 문제는 더 효율있게 풀 수 있는 알고리즘이 있다는 것.

• (대안) 투 포인터로 풀기
  -중복을 만나면, 리턴해서 순회를 중단 + 새로운 start idx로 다시 순회 시작 + 전체 중복 체크
  방식으로 풀었었는데 투 포인터를 이용하면 훨씬 간단하다.

풀이 - 투 포인터

신경 쓴 부분

• 중복 문자를 발견하면, 그 중복 문자 다음으로 아예 시작 위치를 옮기는 것.
  어차피 더이상 순회 안함 + 새로운 배열 갱신 + 그 중에서 길이 최대 구하는 게 목적이기 떼문에 투 포인터로 풀어도 충분

• 문자 길이 세기 = right-left +1
  -인덱스가 0부터 시작되기 때문에 +1해주어야 길이 나옴

• 문자열의 중복 여부를 체크할 때는 ASCII 배열 (최대 128) 만들어 문자 자체를 인덱스로 지정하고 해싱 기법으로 문자의 위치를 저장

• 중복 발견 전까지는 계속 문자를 더해가며 순회하다가, 중복 발견하면 그 즉시 다음 인덱스로 left포인트를 이동시킴.

• 순회 반복

상세 풀이

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] lastPosition = new int[128];
        int left=0;
        int max=0;
        for(int i=0;i<s.length();i++){
            left = Math.max(left,lastPosition[s.charAt(i)]);
            max = Math.max(max,i-left+1);
            lastPosition[s.charAt(i)] = i+1;
        }
        return max;
    }
}