3. Longest Substring Without Repeating Characters

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

Longest Substring Without Repeating Characters - LeetCode

난이도: Medium

 

Given a string, find the length of the longest substring without repeating characters.

 

문자열이 주어졌을 때, 해당 문자열에서 겹치는 문자가 없는 최대 길이를 구하는 문제이다.

 

가장 먼저 떠오른 방법은 substring을 들고 진행하며 linear search를 통해 매번 substring을 모두 탐색하는 방법이다.

python이었다면 해당 index를 찾고, 통째로 삭제하는 과정이 편했겠지만,

java를 사용하여 구현하려다 보니 ArrayList에서 제공하는 기능만으로 코딩하느라 약간 번거로웠다.

 

먼저 문제를 풀기 전에 흐름도를 그려 접근하니 풀이가 수월했다.

간략하게 표현하면 아래와 같다.

커서는 전체 문자열에서 현재 살펴보고 있는 위치이고,

holding은 현재 들고 있는 substring이다.

 

커서의 값이 holding에 존재하는가?	no) ↓
yes) 존재하는 값까지 holding에서 삭제한다. →	holding에 커서의 값을 추가한다. ↓
	최대 길이를 갱신한다.

 

import java.util.ArrayList;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        ArrayList<Character> holding = new ArrayList<Character>();
        
        for (int i = 0; i < s.length(); i++) {
            char newOne = s.charAt(i);
            
            for (int j = 0; j < holding.size(); j++) {
                if (holding.get(j) == newOne) {
                    for (int k = 0; k < j + 1; k++) {
                        holding.remove(0);
                    }
                    break;
                }
            }
            holding.add(newOne);
            
            if (holding.size() > maxLength) {
                maxLength = holding.size();
            }
        }
        return maxLength;
    }
}

 

예시 답안에서는 HashSet을 사용하여 더 효율적으로 구현했다.

등장한 글자를 hash set에 삽입하면서 새로운 글자가 포함되어 있는지만 확인하고,

위치 정보를 int값으로 가지고 가면서 불필요한 반복문을 줄였다.

결국 중요한 것은 반복되는 값이 없는 substring의 길이 뿐이라는 사실에 집중하여 효율을 높였다.

문제를 풀기 전에 꼭 구해야 하는 것이 무엇인지에 대해 집중하는 것도 중요하겠다.