[Java] LeetCode 3번 Longest Substring Without Repeating Characters

반복되는 문자가 없는 가장긴 부분문자열(substring)의 길이를 구하는 문제이다.

for문으로 순차적으로 문자를 탐색하면서 map 언제 마지막으로 해당 문자를 마주쳤는지 저장한다. 만약 마주친 문자가 나온다면 마주친 문자의 개수가 부분문자열의 길이가 된다. 그리고 마주친 문자가 이전에 등장한 위치 + 1 부터 현재위치까지 map을 이용해 마주친 문자들을 넣어준다.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        Map<String, Integer> visitedPos = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            Integer lastPos = visitedPos.get(Character.toString(s.charAt(i)));
            if (lastPos != null) {
                ans = Math.max(visitedPos.size(), ans);
                visitedPos = new HashMap<>();
                for (int j = lastPos + 1; j < i; j++) {
                    visitedPos.put(Character.toString(s.charAt(j)), j);
                }
            }
            visitedPos.put(Character.toString(s.charAt(i)), i);
        }
        ans = Math.max(visitedPos.size(), ans);
        return ans;
    }
}