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

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

Longest Substring Without Repeating Characters - LeetCode

---

문제

Given a string s, find the length of the longest 

substring

 without repeating characters.

 

Example 1:

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

Example 2:

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

Example 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.

 

Constraints:

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

---

풀이

풀이 과정

알파벳, 숫자, 공백으로 이루어진 문자열 s가 주어질 때, 중복된 문자를 가지지 않는 가장 긴 연속되는 부분 문자열의 길이를 구하는 문제이다.

중복되는 문자를 판단하기 위한 map과 시작, 종료인덱스 투 포인터를 이용하여 풀이한다.

우선 최종적으로 반환할 문자열의 최대 길이 변수와 탐색에 사용할 map, start, end 변수를 선언한다.

// 문자열 최대 길이
int maxLength = 0;
// 이미 나온 문자를 탐색하기 위한 map
// 탐색한 문자와 그 문자의 인덱스를 저장
Map<Character, Integer> map = new HashMap<>();
int start = 0;  // 탐색할 문자열의 시작 인덱스
int end = 0;    // 탐색할 문자열의 종료 인덱스

 

탐색 과정은 아래와 같다.

• end 포인터가 문자열의 끝에 도달하거나 앞으로 탐색할 문자열의 길이가 maxLength 이하가 될 때까지 반복한다.
• 처음 탐색하는 문자인 경우 map에 현재 탐색중인 문자와 그 인덱스 값을 저장한다.
• 이미 탐색했던 문자인 경우 이전에 등장했던 인덱스의 다음 인덱스와 현재 start 인덱스 중 큰 값으로 start를 갱신하고 현재 문자의 등장 인덱스를 갱신한다.
• 현재 만들어진 문자열의 길이와 최대 길이를 비교하여 최대 길이를 갱신한다.
• 종료 인덱스를 증가시킨다.

// 문자열을 끝까지 탐색하거나
// 탐색할 문자열의 길이가 maxLength 이하가 될 때 까지 반복
while(end < s.length() && maxLength <= s.length() - start) {
    char letter = s.charAt(end);
    // 처음 탐색하는 문자인 경우
    if(map.get(letter) == null) {
        // map에 현재 탐색중인 문자와 그 인덱스 값을 저장
        map.put(letter, end);
    }
    // 이미 탐색했던 문자인 경우
    else {
        // 이전에 등장했던 인덱스 다음 인덱스와 현재 start 인덱스 중 큰값으로 start 인덱스를 갱신
        start = Math.max(map.get(letter) + 1, start);
        // 현재 문자의 인덱스를 갱신
        map.put(letter, end);
    }
    // 현재 만들어진 문자열의 길이와 최대 길이를 비교하여 최대 길이 갱신
    maxLength = Math.max(maxLength, end - start + 1);
    end++; // 종료 인덱스 증가
}

 

최종적으로 구해진 최대 길이를 return한다.

// 최대 문자열의 길이를 return
return maxLength;

---

최종 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 문자열 최대 길이
        int maxLength = 0;
        // 이미 나온 문자를 탐색하기 위한 map
        // 탐색한 문자와 그 문자의 인덱스를 저장
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;  // 탐색할 문자열의 시작 인덱스
        int end = 0;    // 탐색할 문자열의 종료 인덱스
        
        // 문자열을 끝까지 탐색하거나
        // 탐색할 문자열의 길이가 maxLength 이하가 될 때 까지 반복
        while(end < s.length() && maxLength <= s.length() - start) {
            char letter = s.charAt(end);
            // 처음 탐색하는 문자인 경우
            if(map.get(letter) == null) {
                // map에 현재 탐색중인 문자와 그 인덱스 값을 저장
                map.put(letter, end);
            }
            // 이미 탐색했던 문자인 경우
            else {
                // 이전에 등장했던 인덱스 다음 인덱스와 현재 start 인덱스 중 큰값으로 start 인덱스를 갱신
                start = Math.max(map.get(letter) + 1, start);
                // 현재 문자의 인덱스를 갱신
                map.put(letter, end);
            }
            // 현재 만들어진 문자열의 길이와 최대 길이를 비교하여 최대 길이 갱신
            maxLength = Math.max(maxLength, end - start + 1);
            end++; // 종료 인덱스 증가
        }
        
        // 최대 문자열의 길이를 return
        return maxLength;
    }
}

---