[LeetCode] Longest Substring Without Repeating Characters( 중복 문자 없는 가장 긴 부분 문자열 )

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

Longest Substring Without Repeating Characters - LeetCode

주어진 문자열에서 중복이 없는 문자열의 최대길이가 얼마인지 뽑아내는 문제이다.

투포인트를 사용해 문제를 풀어보려 한다.

• 문자열에 아무것도 없다면 0을 반환해준다.
• 포인터 두 개(p1, p2)를 설정한다.
• 중복되지 않을 문자열을 저장 할 word 딕셔너리를 생성해준다.
  • 이곳의 키 값은 문자길이가 될 것이고 밸류는 그 길이에 중복되지 않은 문자열이 될 것이다. { 3 : ['abc', 'bcd'] } 이런식으로 들어 갈 것이다.
• 전체 길이가 아닌 포인터가 지정된 문자열만 확인한다. 
  • 지정된 문자열의 문자의 갯수를 세어준다.
  • 이때 문자 갯수를 저장하고 있는 딕셔너리에 1만 들어가 있으면 중복된 문자열이 없는 것으로
    • 문자열의 길이에 값이 없으면 리스트를 만들어 추가해주고
    • 문자열 길이에 값이 이미 있으면 존재하는 리스트에 값을 추가해준다.
    • 그 다음으로 p2의 포인터를 이동해준다.
    • 만약 p2의 포인터가 끝에 다다르면 p1의 포인터를 이동시켜준다.
  • 문자 갯수를 저장하고 있는 딕셔너리에 1 이상이 포함되어있다면 중복되는 문자열을 발생하는 것으로 p1 포인터를 이동시켜준다.
  • 모든 문자열을 다 살펴보았으면 keys 값 중 가장 값이 큰 것이 최대 길이가 될 것이다.

 

---

<코드>

• 빈 문자열이 들어왔을때 바로 0을 반환해준다.

if S == "":
	return 0

 

• 포인터 두 개(p1, p2) 을 지정해주어 지정된 문자열의 문자 갯수를 세도록 했다.

		p1, p2 = 0, 0
        word = {}
        while p1 <= len(S) - 1:
            char = S[p1:p2 + 1]
            count = collections.Counter(char).values()

• 지정된 문자열의 각 문자를 카운트 했을때 1만 존재하면 그 문자열은 중복되지 않은 문자열
  • 딕셔너리에 이미 해당 카운트에 대해 값이 존재한다면 그 value에 append를 해주기로 한다.
  • 딕셔너리에 값이 없는 경우 value에 새로운 리스트를 선언하여 값을 추가해주도록 한다.

	if all(x == 1 for x in count):
                if len(char) in word.keys():
                    if all(x != char for x in word[len(char)]):
                        word[len(char)].append(char)
                else:
                    word[len(char)] = list()
                    word[len(char)].append(char)

* 만약 p2가 끝까지 도달했다면 p1이 증가하도록 했고 그렇지 않으면 p1이 증가하도록 했다.

		if (p2 == len(S) - 1):
                    p1 += 1
                else:
                    p2 += 1

 

* 문자를 카운트했을때 1 이상인 숫자가 들어있다면 문자열에 중복된 문자가 들어간 것이기 때문에 p1을 증가하도록 해주었다.

	else:
                p1 += 1

 

* while문이 끝나면 word 딕셔너리에 중복되지 않은 문자열들이 저장되어 있을 것이다. 거기에서 최대 길이를 반환해준다.

	if word.keys():
            return max(word.keys())
        else:
            return 0

 

전체코드

class Solution:
    def lengthOfLongestSubstring(self,S:str) -> int:
        if S == "":
            return 0
        p1, p2 = 0, 0
        word = {}
        while p1 <= len(S) - 1:
            char = S[p1:p2 + 1]
            count = collections.Counter(char).values()

            if all(x == 1 for x in count):
                if len(char) in word.keys():
                    if all(x != char for x in word[len(char)]):
                        word[len(char)].append(char)
                else:
                    word[len(char)] = list()
                    word[len(char)].append(char)
                if (p2 == len(S) - 1):
                    p1 += 1
                else:
                    p2 += 1
            else:
                p1 += 1
        
        if word.keys():
            return max(word.keys())
        else:
            return 0

 

이렇게 짜본 이유는 최대 길이를 가진 문자열을 반환하는 것이라 생각해서 짜보았다.

통과는 되었지만 성능은 좋지 못하다. 최대 길이만 출력되도록 코드를 다시 수정해보자

 

---

최대 길이만 구하는 코드로 수정

 

import collections

class Solution:
    def lengthOfLongestSubstring(S:str) -> int:
        if S == "":
            return 0

        start, end = 0, 0
        word = {}
        max_len = 0
        while start <= len(S) -1:
            char = S[start:end + 1]
            count = collections.Counter(char).values()

            if all(x == 1 for x in count):
                if(max_len < len(char)):
                    max_len = len(char)
                if end == len(S)-1 :
                    start += 1
                else:
                    end += 1
            else:
                start += 1
        return max_len