3. Longest Substring Without Repeating Characters, 자바 풀이

[문제]
Given a string s, find the length of the longest substring without repeating characters.

https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public int lengthOfLongestSubstring(String s) {

        HashMap<Character, Integer> visited = new HashMap<>();
        int l = 0;
        int r = 1;
        int max_val;

        if (s.length() == 0) {
            return 0;
        } else {
            max_val = 1;
        }

        char[] c = s.toCharArray();
        visited.put(c[l], 1);

        for (int i = 1; i < s.length(); i++) {
            if (visited.get(c[i]) != null) {
                continue;
            }

            visited.put(c[i], 0);
        }


        while (l <= r && r < s.length()) {
            if (visited.get(c[r]) == 1) {
                visited.put(c[l], visited.get(c[l]) - 1);
                l++;
            } else {
                max_val = Math.max(max_val, r - l + 1);
                visited.put(c[r], visited.get(c[r]) + 1);
                r++;
            }
        }


        return max_val;
    }
}

// 반복하지 않는 가장 긴 부분 문자열

//   v v v
// a b c b a c b b
// 중복되지 않는 부분문자열인 경우에만 최대 길이를 저장한다.

// left는 지우는 과정
// right는 추가하는 과정이기 때문에, 중복시에 right는 고정하고 left를 중복이 없어질때까지 줄임.

// "abcabcbb"

반복하지 않는 가장 긴 부분 문자열을 구하는 문제이다. 투 포인터 유형으로 해결할 수 있었다.

중복의 판별을위해 HashMap을 사용했다. 문자열을 문자형 배열로 변환시킨 뒤, 각 요소들의 중복을 피해 map에 저장하자.
l, r 포인터를 사용하여, 증가하는 r 포인터의 문자가 중복 값이라면 map에 기록하였던 l의 value값을 0으로 감소시키고, l을 증가시킨다.