[java] Longest Substring Without Repeating Characters

[참고 문제] : https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

---

문제 풀이

생각의 흐름 - 저장하자.

필요한 건 가장 긴 길이가 무엇이냐? 그리고 이 문자가 나왔는가?

이 2가지를 저장할 필요가 있었다.

가장 긴 길이 여부는 max 계산을 하고, 이 문자가 이미 나왔는지 여부는 Map에 저장하자고 판단.

 

생각의 흐름 - 언제 초기화를 하는가?

Loop를 돌면서, map이 가지고 있는지 확인한다.

그리고, 없으면 현재 길이를 늘리면서, map에 저장한다.

있다면, 1. max 여부를 판단, 2. 현재 길이 초기화, 3. map 초기화

 

생각의 흐름 - 어디부터 다시 확인해야 하는가?

가장 긴 길이를 확인할 때, 이미 나왔던 문자가 다시 나왔다면, 어디부터 시작해야하는지 고민해야 했다.

해당 문자가 처음 나온곳부터 계산하면 되겠다고 판단, Map의 Value에 Index를 저장하기로 판단.

 

생각의 흐름 - 초기화를 항상 하는가?

마지막 문자까지 간 경우도 고민해주어야 하기에, return 시에 한번 더 max 체크하는 로직을 넣었다.

 

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    int currLen = 0;
    Map<Character, Integer> map = new HashMap<>();
    for(int i = 0; i < s.length(); i++) {
        if(map.containsKey(s.charAt(i))) {
            max = Math.max(max, currLen);
            currLen = 0;
            i = map.get(s.charAt(i));
            map.clear();
        } else {
            map.put(s.charAt(i), i);
            currLen ++;
        }
    }
    return Math.max(currLen, max);
}