LeetCode 3. Longest Substring Without Repeating Characters

문제 : 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라. (링크)

 

풀이내용:

 이 문제는 O(n)에 풀이가 가능하다.

O(n) 풀이를 위해서는 '투 포인터'와 '슬라이딩 윈도우'를 이용해 길이를 구해야 한다.

 

"abcabcbbc" 와 같은 문자열이 있다. (String s = "abcabcbbc")

s의 0번째 인덱스인 a부터 2번째 인덱스 까지는 중복이 없다.

이 범위는 left라는 포인터와 right라는 포인터의 범위를 조정해 left: 0, right: 2 의 값으로 길이를 구한다.

3번째 인덱스 a를 순회할 때 '0번째 인덱스'에 'a'가 있다는 것을 알아야한다.

중복 글자를 제외한 범위로 left를 조정하고 다시 조건에 해당하는 글자의 길이수를 계산한다.

위 과정이 반복되는 중에 right 포인터의 값은 계속해서 1씩 증가한다.

 

풀이구현:

필요변수는 아래와 같다.

// 조회한 글자와 해당 글자의 인덱스를 저장할 변수를 선언
Map<Character, Integer> used = new HashMap<>();

// 중복된 글자가 없는 문자열의 길이를 저장할 변수 선언
int maxLength = 0;

// 왼쪽, 오른쪽 포인터
// 이 포인터의 값을 이용해 maxLength의 값을 계산한다.
int left = 0, right = 0;

 

중복되지 않은 문자열과 길이 구하기

for (char c : s.toCharArray()) {
    // Map 자료형에 해당 글자가 있고 포인터가 그 글자의 인덱스 보다 작거나 같은 경우는 중복된 글자이다
    if (used.containsKey(c) && left <= used.get(c)) {
        // 따라서 left의 값을 해당 글자 인덱스로부터 1 더한값으로 저장한다
        // 즉, left를 해당 글자가 있는 곳의 인덱스 바로 다음 위치로 이동한다.
        left = used.get(c) + 1;
    } else {
        // 중복된 글자가 아닐 경우 두 포인터를 이용한 계산의 값과
        // 현재까지 저장된 가장 긴 길이를 비교하여 maxLength에 대입
        maxLength = Math.max(maxLength, right - left + 1);
    }
    // 조회한 글자는 인덱스와 글자를 Map에 저장한다
    used.put(c, right);
    right++;
}

 

전문은 아래와 같다.

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

        for (char c : s.toCharArray()) {
            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++;
        }
        return maxLength;
    }
}