[LeetCode] 3. Longest Substring Without Repeating Characters -문제풀이

Description

문자열에서 중복되지 않은 문자열을 가진 최대로 연속된 문자열의 길이를 반환하는 문제입니다.

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Solution 1. Sliding Window - ASCII 배열

public int lengthOfLongestSubstring(String s) {
    int[] chars = new int[128]; // 해당 문자의 중복여부 확인 + 마지막 위치를 저장하기 위함
    Arrays.fill(chars, -1);  // 인덱스를 저장할 것이기 때문에 초기값 0을 -1로 바꿔줌
    int len = s.length();
    int max = 0;
    int start = 0;
    for (int i=0; i < len; i++) { 
        if(chars[s.charAt(i)] >= start){ // 현재 문자가 시작점 이후에 사용됐을 경우 중복.
            start = chars[s.charAt(i)]+1; // 중복된 문자의 마지막위치 +1로 start인덱스 이동
        }
        chars[s.charAt(i)] = i;         // 해당 문자의 마지막 위치 기록
        max = Math.max(max,i-start+1); // 유효한 최대 길이 계산. 진행중인 i에서 start까지의 거리
    }
    return max;
}

슬라이딩윈도우(Sliding Window) 알고리즘을 적용하여 이미 검사한 서브 배열의 중복되지 않는 요소들은 패스하며 포인터만 옮겨서 처리하면 O(N)의 시간복잡도로 처리가 가능합니다. 배열에 각 ASCII char 번호를 인덱스로 하여 마지막 위치를 저장하고 중복되는 케이스가 나올 경우마다 start인덱스를 중복되는 문자+1로 옮겨가며 최대로 긴 길이(max)를 반환합니다.

Solution 2. Sliding Window - HashMap

public int lengthOfLongestSubstring(String s) {
    HashMap<Character,Integer> map = new HashMap<>(); // 해당 문자의 중복여부 확인 + 마지막 위치를 저장하기 위함
    int len = s.length();
    int max = 0;
    int start = 0;
    for (int i=0; i < len; i++) { 
        if(map.get(s.charAt(i))!=null && map.get(s.charAt(i)) >= start){
            start = map.get(s.charAt(i))+1; // 중복된 문자의 마지막위치 +1로 start인덱스 이동
        }
        map.put(s.charAt(i),i);         // 해당 문자의 마지막 위치 기록
        max = Math.max(max,i-start+1); // 유효한 최대 길이 계산. 진행중인 i에서 start까지의 거리
    }
    return max;
}

컨셉을 Solution1과 동일하고 마지막위치 저장, 중복여부 체크를 위하여 ASCII Array대신 HashMap을 사용했습니다. Set나 다른 자료구조를 사용해도 유사하게 처리가 가능합니다.

Solution 3. 전체 순회

public int lengthOfLongestSubstring(String s) {
    int len = s.length();
    StringBuilder sb = new StringBuilder();
    String result = new String();

    for (int i = 0; i < len; i++) {
        for (int j = i; j < len; j++) {
            if(sb.indexOf(String.valueOf(s.charAt(j))) > -1){
                if(result.length() < sb.length()){
                    result = sb.toString();
                }
                sb.setLength(0);//초기화
                break;
            }else{
                sb.append(s.charAt(j));
                if(j==len-1 && result.length() < sb.length()){  //last case
                    result = sb.toString();
                }
            }
        }
    }
    return result.length();
}

이중포문을 돌며 각 모든 문자열별로 경우의 수를 찾아내는 소스 입니다. 시간복잡도가 O(n^2)로 한 번 돌려 봤는데 163ms로 통과하긴 하네요.

Reference

Longest Substring Without Repeating Characters - LeetCode