[LeetCode/MEDIUM] 3. Longest Substring Without Repeating Characters (JAVA) : 문제&풀이

 

반복없이 가장 긴 문자열의 길이를리스트로 반환하는 문제이다.
 
String을 매개변수로 받는 lengthOfLongestSubstring메서드의 틀이 주어진다.

 

Problem :

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {

    }
}

풀이는 lengthOfLongestSubstring 메서드에 작성하면 된다.
 

Solution 1: HashSet을 사용하는 방법

1. 왼쪽/오른쪽 포인터, 최대 길이 값을 담을 int 변수를 초기화 한다.

    고유문자를 담을 Set 변수을 초기화한다.

2. 오른쪽 포인터가 문자열 끝에 닿을 때까지 반복할 때,

    1) 오른쪽 포인터의 문자가 고유문자Set에 없으면, 추가하고 포인터를 하나 늘린다.

        이 때, 현재까지의 최대 길이와 고유문자 길이 Set의 길이 중 더 긴 것을 최대 길이로 갱신한다.

    2) 만약 오른쪽 포인터의 문자가 고유문자Set에 있었다면 왼쪽 포인터의 문자를 Set에서 제거한다.
        (오른쪽 포인터는 바뀌지 않기 때문에 중복이 발생한 오른쪽 포인터의 글자를 지울 때까지 왼쪽 포인터가 이동함)

public int lengthOfLongestSubstring(String s) {

    // init
    int left = 0, right = 0, max = 0;
    Set<Character> uniqueSet = new HashSet<>();

    // loop
    while (right < s.length()) {
        if (!uniqueSet.contains(s.charAt(right))) {
            uniqueSet.add(s.charAt(right++));
            max = Math.max(max, uniqueSet.size());
        } else {
            uniqueSet.remove(s.charAt(left++));
        }
    }

    return max;
}

 

예를 들면, abbcba는 다음과 같은 순서를 거쳐 max = 3을 반환하게 된다.

 

Solution 2: Map을 사용하는 방법

1. 주어진 문자열이 없으면 최대 길이 0을 반환한다.
    주어진 문자열이 한 글자이면 1을 반환한다.

2. 그 이상인 경우, 최대 길이가 1이상이므로

    고유문자별 인덱스Map에 첫번째 글자를 넣고, 왼쪽/오른쪽 포인터를 각각 0과 1에 둔다.

3. 오른쪽 포인터가 문자열 끝에 닿을 때까지 반복할 때,

    1) Map에 오른쪽 포인터의 문자(key)가 있고, 그 인덱스(value)가 왼쪽 포인터 이상인 경우,
        (Map에 저장된 문자의 인덱스와 왼쪽 포인터를 비교하는 이유는 이미 중복으로 열외했던 자릿수는 제외하기 위함)
        왼쪽 포인터를 Map에 해당 문자의 인덱스 다음 자리까지 이동한다.

    2) 그 외는 새로운 문자가 추가된 것이므로,

        지금까지의 최대 길이와 현재 문자열(왼쪽포인터~오른쪽포인터) 길이 중 더 긴 것을 최대 길이로 갱신한다.

    3) 현재의 대상 문자를 현재 인덱스와 함께 Map에 추가 혹은 갱신하고, 오른쪽 포인터를 한 칸 더 이동한다.

public int lengthOfLongestSubstring(String s) {

    // in case no string given
    if (s == null || s.length() == 0) return 0;
    if (s.length() == 1) return 1;

    // init variables
    int max = 1;
    int left = 0, right = 1;
    Map<Character, Integer> uniqueCharMap = new HashMap<>();
    uniqueCharMap.put(s.charAt(left), left);
    
    while(right < s.length()) {
        char c = s.charAt(right);
        if (uniqueCharMap.containsKey(c) && uniqueCharMap.get(c) >= left) {
            left = uniqueCharMap.get(c) + 1;
        } else {
            max = Math.max(max, (right - left + 1));
        }
        uniqueCharMap.put(c, right);
        right++;
    }

    return max;
}

예를 들면, abbcba는 다음과 같은 순서를 거쳐 max = 3을 반환하게 된다. 

 

TestCase :

abcabcbb
bbbbb
pwwkew
abcadertb
a
abbcba
abcba

 
위 테스트 케이스의 Output은 다음과 같다.

3
1
3
7
1
3
3