[LeetCode/Java] 3. Longest Substring Without Repeating Characters

yuKeon·2023년 8월 28일

LeetCode

목록 보기

11/29

0. 문제

https://leetcode.com/problems/longest-substring-without-repeating-characters/

1. 문제 설명

문자열 s가 주어진다.
중복 없이 만들 수 있는 가장 긴 부분 문자열을 구하라.

2. 문제 풀이

2.1. 접근법

투 포인터와 Map을 사용해서 O(n)의 시간 복잡도로 해결한다.
문자를 조회하면서 Map에 저장한다.
Map에 저장 시 Key는 문자가 되고 Value는 인덱스 번호를 저장한다.
Map에 있는 문자를 발견하면 tail 값과 Map의 Value 값을 갱신한다.
최대 길이를 계산한다.

3. 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        
        Map<String, Integer> map = new HashMap();
        int ans = Integer.MIN_VALUE;
        int tail = 0;
        
        for (int head = 0; head < s.length(); head++) {
            String tmp = Character.toString(s.charAt(head));
            if (map.containsKey(tmp)) tail = Math.max(tail, map.get(tmp) + 1);
            map.put(tmp, head);
            ans = Math.max(ans, head - tail + 1);
        }
        return ans;
    }
}