Longest Substring without Repeating Characters: HashMap

First Thoughts

Sliding Window가 떠올랐다. 일단 반복되는 문자가 없어야함으로 최대길이를 업데이트 해가면서 길이를 세는 형식. 시작점을 반복되는 문자 하나 다음으로 옮기면서 간다. 길이는 시작점-마지막점+1 형식으로 계산할 수 있다. 특정 문자의 마지막 점은 retrieve, put 시간 효율성이 좋은 hashmap으로 하면 좋겠다.

Solution

public int lengthOfLongestSubstring(String s) {
	int maxLength = 0;
    int startPoint = 0;
    HashMap<Character, Integer> chars = new HashMap<>();
    for (int endPoint=0; endPoint<s.length(); endPoint++) {
    	char c = s.charAt(endPoint);
    	if (chars.containsKey(c))
        	startPoint = Math.max(startPoint, map.get(c)+1);
        map.put(c, endPoint);
        maxLength = Math.max(maxLength, startPoint-endPoint+1);
    }
    return maxLength;
}

Catch Point

1. startPoint는 항상 전의 endPoint+1이라고 생각했다. 하지만 endPoint+1 < startPoint인 경우 (앞지른 경우)도 생각해줘야 한다.

2. 문자를 처음 본 경우, startingPoint가 업데이트된다. 그게 아니라면 그대로 고정이며 endPoint만 하나씩 늘어난다.

3. endPoint를 포함한 hashmap과 maxLength 는 항상 업데이트해줘야한다.

4. 길이를 index를 사용해 track하면 매우 편리해진다. index는 hashmap에서 쉽게 O(1)으로 불러올 수 있기 때문에 효율적이다.