LeetCode (3) - Longest Substring Without Repeating Characters

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- Longest Substring Without Repeating Characters

• Acceptance: 32.8%
• Difficulty: Medium

문제 설명

String s에서 중복되는 글자가 없는 가장 긴 substring의 길이를 구하여라

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces

예시 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

예시 2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

예시 3

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

문제 풀이

• 중복되는 문자가 없으므로 Map에 Character를 넣으면 Map size가 substring의 length와 같다.
  * Key: Character, Value: index를 저장한다.
• for문을 이용해 Character를 확인하며 Map에 데이터를 넣는다.
• Character가 Map에 존재하는 경우
  1. result를 Map size와 비교해서 큰 값으로 저장한다.
  2. index를 이전 중복된 Character의 index + 1로 설정한다. -> vbvf인 경우 두번째 v에서 걸렸을 때, b부터 다시 시작해야하기 때문
  3. 새로운 substring이 시작하므로 Map clear
• 마지막에 한번 더 Map size와 result를 비교하여 큰 값을 return

코드

import java.util.HashMap;
import java.util.Map;

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

        for (int i = 0, sLength = s.length(); i < sLength; i++) {
            if (map.containsKey(s.charAt(i))) {
                result = Math.max(result, map.size());
                i = map.get(s.charAt(i)) + 1;
                map.clear();
            }

            map.put(s.charAt(i), i);
        }
        return Math.max(result, map.size());
    }
}