[java] Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

 

문제 풀이

MAP을 써야 하는 문제라는 걸 인식했다.

 

생각의 흐름 - MAP을 어떻게 구성할까?

인덱스를 갖고 있어야 한다고 생각했다. 똑같은게 나왔을 때, 기존 인덱스를 어떻게든 활용해야 한다고 생각했다.

 

생각의 흐름 - 현재의 흐름과 최대값의 흐름을 별도로 가져가야 한다.

최대값은 반환값을 위해, 그리고 계산을 위해 현재 값도 갖고 가면서 비교해야 한다고 판단했다.

 

생각의 흐름 - if문을 어떻게 구성할까?

MAP에 있는지 없는지를 비교하는건 자명했다.

MAP에 없을 때는 값을 넣어주어야 하고 현재 길이를 늘린다.

MAP에 있을 때가 주요한 것으로 보였다.

이미 MAP에 있다면 현재 크기와 최대값을 비교해서 저장해야 했다.

그렇다면, 그 이후는 어디부터 계산해야할까?

단순히 계속 나가는 건 advdf 와 같은 예시에서 틀리기 마련이다.

바로 이전에 나온 위치. 즉, 앞서 고민했던 기존 인덱스 다음부터 계산을 했어야 한다.

그럼 어떻게 돌아가야 할까? i를 그냥 돌려버리면 된다.

 

생각의 흐름 - return 값은?

누락해버린 것이 있었다.

currLen을 maxLen과 비교안해버리는 경우가 있었다.

이를 최종적으로 처리해준다.

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