[LeetCode] #3 Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

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

 

중복되는 알파벳이 없는 가장 최장의 substring을 구하라는 문제이다.

내 풀이부터 우선 보자.

 

x
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int answer = 0;
        String tmp = "";
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (tmp.contains("" + c)) {
                tmp = tmp.substring(1);
                i--;
            } else {
                tmp += c;
                if (answer < tmp.length())
                    answer = tmp.length();
            }
        }
        
        return answer;
    }
}

 

문자열을 앞에서부터 하나하나 추가한다.

겹치는 문자가 나오면 안나올때까지 앞부분을 소거해나간다.

소거할만큼 한 뒤에는 다시 하나하나 추가해나간다.

추가할때마다 문자열 길이를 체크해서 가장 긴 길이를 리턴한다.

 

문자열 소거하는 타이밍, 추가하는 타이밍을 헤매서 조금 걸렸는데, 재밌는 문제였다.

Hash Set이라던지, ArrayList를 사용하는 사람들도 많았다.

나도 Deque를 사용해서 풀었으면 더 재밌었을것같다.