박종훈 알고리즘 블로그

(Leetcode) 3 - Longest Substring Without Repeating Characters

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


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

문자열과 관련된 문제이다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0

        characters = list(s)
        longest = -1

        def findLongestSubstring(start):
            exist = {}
            length = 0
            for i in range(start, len(characters)):
                if characters[i] in exist:
                    return length
                else:
                    exist[characters[i]] = True
                    length += 1
            return length

        for i, char in enumerate(characters):
            longest = max(longest, findLongestSubstring(i))

        return longest

한번에 통과는 하였지만 매우 결과가 안좋게 나왔다.

그래서 다른 사람의 코드를 확인해보았다.

다른 사람들이 푼 방식

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0

        temp = []
        longest = 0

        for char in s:
            if char in temp:
                temp = temp[temp.index(char) + 1:]
            temp.append(char)
            longest = max(longest, len(temp))

        return longest

똑똑하게 접근한 것 같다.

temp를 통해 최대로 긴 문자열을 저장해두고, 동일한 글자가 나오면 앞에서 해당 글자를 제거하고 뒤에 해당 글자를 추가하는 방식을 택하였다.

Java로 다시 풀어보기 (queue를 사용해서 풀기) (240603)

위 글을 보지 않고 자바로 다시 풀어봤다.

public int lengthOfLongestSubstring(String s) {
    if (s.isEmpty()) {
        return 0;
    }

    Queue<Character> queue = new LinkedList<>();
    int start = 0;
    int end = 0;
    int longest = 0;

    while (pointer < s.length()) {
        char _char = s.charAt(pointer);
        while (queue.contains(_char)) {
            queue.remove();
        }
        queue.add(_char);
        longest = Math.max(longest, queue.size());
        pointer++;
    }

    return longest;
}

TC, SC

시간 복잡도는 O(n^2) 이고, 공간 복잡도는 O(n) 이다.

retry result

아무래도 시간을 더 줄여줘야 할 것 같다.

좀 더 최적화 해보기

contains 에서 시간을 많이 뺏는것 같다는 생각이 들었다. (순회 탐색 하려면 O(n) 이니깐)

중복이 되면 안된다는 점에서 Set을 사용했다.

class Solution {
	public int lengthOfLongestSubstring(String s) {
		if (s.isEmpty()) {
			return 0;
		}

		Set<Character> set = new HashSet<>();
		int pointer = 0;
		int longest = 0;

		while (pointer < s.length()) {
			char _char = s.charAt(pointer);
			while (set.contains(_char)) {
				set.remove(s.charAt(pointer - set.size()));
			}
			set.add(_char);
			longest = Math.max(longest, set.size());
			pointer++;
		}

		return longest;
	}
}

TC, SC

시간 복잡도는 O(n) 이고, 공간 복잡도는 O(n) 이다. 내부 while이 그대로 있지만 O(n)으로 적은 이유는 hash set의 경우 search 하는데 드는 비용이 O(1) 이기 때문이다.

final result

결과적으로 시간이 많이 줄어들었다.

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , string , char , character , 자바 , java , set , hashset , queue