[LeetCode] Longest Substring Without Repeating Characters (Java)

문제

 

문제풀이 과정

1. 카운트배열을 통한 접근

- 문자가 중복되면 안되기 때문에 각 알파벳에 해당하는 불리언 형태의 카운트배열을 만들어놓고 중복값을 마주치면 초기화하도록 구성
- 그리고 failed... 왜지? 문제를 잘못 이해했던 것... 바본가 오랜만에 풀어서 감을 아주 잃어버렸다.
- 우선 예제는 소문자만을 얘기하고 있지만, 조건을 보면 English letters, digits, symbols, spaces 모두 들어갈 수 있다.
   이런 기초적인 실수를 하다니...ㅠ^ㅠ 감이 아주 죽었구나.... 다시다시 풀이 시작

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        int maxLength = 0;
        int cnt = 0;
        boolean[] check = new boolean[26];

        for (int i = 0; i < s.length(); i++) {
            int curr = s.charAt(i) - 'a';
            if(check[curr]) {
                if(cnt > maxLength) {
                    maxLength = cnt;
                    cnt = 1;
                }
                check = new boolean[26];
            } else {
                cnt++;
            }
            check[curr] = true;
        }

        return maxLength;
    }
}

2. Map + 전체 탐색

- 우선 문자열의 길이가 너무 길지 않기 때문에 For문을 통해 시작 index에서 최대한 갈 수 있는 문자열을 구하는 형태로 구현
 1) 문자열이 하나도 없을 경우나 하나만 있을 경우에는 그냥 바로 값을 리턴하게 해줌
 2) 문자열이 2개 이상일 경우에는 가장 긴 문자열의 최소값은 1이므로 1로 초기화하여 시작
 3) 만약 중복 없이 문자열이 쭉 이어질 경우를 대비하여 마지막에 cnt 와 MAX_SUM을 비교하는 작업을 추가해줌

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        if (s.length() == 0) return 0;
        if (s.length() == 1) return 1;

        int maxLength = 1;
        
        for (int i = 0; i < s.length() - 1; i++) {
            int cnt = 1;
            HashMap<Character, Integer> dic = new HashMap<>();
            
            char curr = s.charAt(i);
            dic.put(curr, 1);
            
            for (int j = i + 1; j < s.length(); j++) {
                char next = s.charAt(j);
                if (dic.containsKey(next)) {
                    if (cnt > maxLength) {
                        maxLength = cnt;
                    }
                    break;
                } else {
                    dic.put(next, 1);
                    cnt++;
                }
            }
            
            if (cnt > maxLength) maxLength = cnt;            
        }
        
        return maxLength;
    }
}

- 패스는 했지만, 런타임이 만족스럽지 않은 수준... 그래서 다른 풀이들을 찾아보았다.

3. Set  + Two point 활용

개선방법 1) Map > Set 활용 
- Set은 그 자체로 중복을 허용하지 않기 때문에 코드가 더 명확 (Map에서 쓸데 없는 Value값을 넣어주지 않아도 된다.)
개선방법 2) 전체탐색 > Two point 활용
- 전체 탐색이 아닌, 중복되는 문자열을 만났을 경우 앞쪽에서 해당 문자열을 만날 때까지 포인터를 옮겨준 후 재탐색 진행

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        int maxLength = 0;
        Set<Character> dic = new HashSet<>();

        int st = 0;

        for (int ed = 0; ed < s.length(); ed++) {
            char curr = s.charAt(ed);
            if (!dic.contains(curr)) {
                dic.add(curr);
                maxLength = Math.max(maxLength, ed - st + 1);
            } else {
                while(dic.contains(curr)) {
                    dic.remove(s.charAt(st++));
                }
                dic.add(curr);
            }
        }

        return maxLength;
    
    }
}

 

- 훨씬 단축됐다!!