[자바 알고리즘 인터뷰] ch 11. 해시 테이블 (3) 중복 문자 없는 가장 긴 부분 문자열

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

 

 

- 중복 문자가 없는 가장 긴 부분 문자열(Substirng)의 길이를 리턴하라 

 

 

풀이 1) 슬라이딩 윈도우와 투 포인터로 크기 조절 

 

- 슬라이딩 윈도우로 한 칸씩 우측으로 이동하면서 윈도우 내에 모든 문자가 중복이 없도록 투 포인터로 윈도우 크기를 조절하면서 풀이해보면 다음과 같다. 

 

- 슬라이딩 윈도우의 각 단계별로 중복 문자가 없는 윈도우의 최대 길이를 순서대로 표시했다. 

 

자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

 

- 먼저 투 포인터로 문제를 풀이하되, 포인터 2개 모두 왼쪽에서 출발한다. 

- 각각 왼쪽 시작점에서 출발해 두 번째 포인터(right변수)는 다음과 같이 현재 문자의 위치에 맞춰 계속 증가시킨다. 

for(char c: s.toCharArray())
{
    //이미 등장했던 문자이고, 슬라이딩 윈도우의 안쪽에 있다면 left 위치 업데이트 
    if(used.containsKey(c) && left<=used.get(c))
    {
        left = used.get(c)+1;
    }
    else
    {....
    }

....
    //오른쪽 포인터 right는 현제 문자의 위치에 맞춰 계속 증가 
    right++;
 }

 

 

- 이미 등장한 문자 여부는 used에서 확인하며, 해시맵으로 선언한다. 

- used는 각각의 문자가 등장한 최종 위치(인덱스)를 저장해두는 해시맵이며, 만약 used.containsKey()를 통해 이미 등장했던 문자로 확인되면 왼쪽 포인터 left를 기존에 저장되어 있던 위치의 +1 위치로 업데이트한다. 

 

HashMap<Character,Integer> used = new HashMap<>();

if(used.containsKey(c) && left<=used.get(c))
{
    left = used.get(c)+1;
}

 

- 하지만, 등장하지 않았던, 처음 보는 문자라면 다음과 같이 매번 부분 문자열의 길이를 확인하면서 더 클 경우 최댓값 maxLength를 업데이트 한다. 

//최대 부분 문자열 길이 업데이트
maxLength = Math.max(maxLength, right-left+1);

 

- 오른쪽 포인터 right는 현재 문자의 위치에 맞춰 계속 값을 증가시켜준다. 또한 반복하면서 used에도 현재 문자의 현재 위치를 값으로 삽입한다. 

 

 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> used = new HashMap<>();
        int maxLength = 0;
        int left = 0;
        int right = 0;

        //문자열을 문자 단위로 반복
        for(char c: s.toCharArray())
        {
            //이미 등장했던 문자이고, 슬라이딩 윈도우의 안쪽에 있다면 left 위치 업데이트 
            if(used.containsKey(c) && left<=used.get(c))
            {
                left = used.get(c)+1;
            }
            else
            {
                //최대 부분 문자열 길이 업데이트
                maxLength = Math.max(maxLength, right-left+1);
            }

            //현재 문자의 위치 삽입
            used.put(c,right);

            //오른쪽 포인터 right는 현제 문자의 위치에 맞춰 계속 증가 
            right++;
        }

        return maxLength;
    }
}

5밀리초