3. Longest Substring Without Repeating Characters

Intuition

1. HashMap에 순서대로 값을 하나씩 집어넣는다. (값, 문자열 인덱스)
   • HashMap 사용 이유: 문자열 s도 순서대로 조회해야 하는데, 그 과정에서 기존에 받은 문자가 중복인지 체크할 때 HashMap을 사용하지 않는다면 시간복잡도가 O(n^2)이 되어 너무 길어지기 때문이다.
2. 반복되지 않는 부분이 생기면 count++를 한다.
3. 문자열 s를 순서대로 한 문자씩 받아오면서O(n), HashMap에 있는 이전 문자들과 비교한다. O(1)
4. 만약 count의 값이 1 이상이고, 새로운 문자가 HashMap에 있으면, 바로 loop를 종료하고 count를 반환한다.
   -> 안됨(왜냐: 문자열 전체에서 가장 긴 문자열이어야 함)
5. 문자열 전체를 돌면서 count가 0으로 갱신되는 지점마다 count를 (자료구조 미정) 객체에 저장한다.
6. loop를 다 돌면 (자료구조 미정) 객체에 있는 것들 중 가장 큰 값을 return한다.

Approach

푸는 도중 count를 사용하는 것은 문제와 맞지 않다고 생각했다. 기존 코드의 틀은 최대한 유지하되, window라는 변수를 사용해서 중복이 발생한 곳의 index를 기억하는 방향으로 바꾸었다.
1. 중복이 발생하면->window 갱신
- window의 값을 갱신할 때,
2. 중복이 발생하지 않으면 -> HashMap에 값만 저장
3. 마지막으로 주어진 null이 아닌 경우에, 최솟값 1을 보장하며 return

Complexity

• Time complexity:O(n)
• Space complexity: O(n) <-해시맵 사용
  • 풀고 나서 찾아본 새로운 가능성: ASCII 배열로 처리하기 -> O(1) (wow...)

Code

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charPool = new HashMap<>();
        // int count = 0;
        int maxCount = 0;
        int window = 0; 


        if (s.isEmpty()){
            return 0;
        }
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (charPool.containsKey(c)){  // 반복되는 부분
                
                if (maxCount < i - window){ // count 새로 갱신 
                    maxCount = i - window;
                }
                window = Math.max(window, charPool.get(c)+1);
                charPool.put(c, i);
            }else{ // 반복 안 되는 부분
                charPool.put(c, i);
            }
        }
        // 다 돌고 나서 마지막 문자 기준으로 한 번 더 계산 
        if (maxCount < s.length() - window){ // count 새로 갱신 
            maxCount = s.length() - window;
        }
        // if (charPool.size() >= 1 && window ==0){
        //     return charPool.size();

        return Math.max(maxCount, 1);

    }
}

여담

• 예외가 정말 다양하게 나와서 골치아팠다. 더불어 문자열을 다룰 땐 이런 부분을 미리 고려해야겠다고 느꼈다. 숫자가 아니라 문자가 되니까 난이도가 상승한 기분....
  • 문자가 공백(" ")인 상황
  • 문자가 null("")인 상황