Leetcode#3_Longest Substring Without Repeating Characters _05wk01 by SOMJANG

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

---

Solution by SOMJANG

class Solution:
    def lengthOfLongestSubstring(self, my_str: str) -> int:
        answer = 0
        
        substrings = []
        
        my_str_list = list(my_str)
        
        set_list = set(my_str_list)
        
        if len(set_list) == 0:
            answer = 0
        elif len(set_list) == 1:
            answer = 1
        else:
            for i in range(len(my_str_list)):
                sub = []
                for j in range(i, len(my_str_list)):
                    if my_str_list[j] in sub:
                        substring = ''.join(sub)
                        substrings.append(len(substring))
                        break
                    sub.append(my_str_list[j])
                    
                    if j == len(my_str_list) - 1:
                        substring = ''.join(sub)
                        substrings.append(len(substring))

            answer = max(substrings)
                            
        return answer

 

---

Solution 풀이

이 문제는 문자열 안에서 반복되는 문자가 없는 부분 문자열 중 가장 긴 부분 문자열의 길이를 구하는 문제입니다.

먼저 부분 문자열들의 길이를 구하여 저장해 둘 substrings 라는 비어있는 리스트를 하나 만들어 줍니다.

 

그 다음 함수에서 인자로 받은 my_str 문자열을 리스트로 만들어 my_str_list로 만들어줍니다.

ex ) my_str이 "aaabcd" 일 경우 -> my_str_list = list(my_str) -> my_str_list는 ["a", "a", "a", "b", "c", "d"]

그리고 my_str_list에 set을 씌워서 중복된 값이 없는 리스트도 하나 만들어 줍니다.

ex ) my_str_list가 ["a", "a", "a", "b", "c", "d"] 일 경우 -> set_list = set(my_str_list)

     -> set_list 는 ["a", "b", "c", "d"]

여기서 만든 set_list를 가지고

인자로 받은 문자열이 모두 같은 문자로 이루어져 있는지

ex) my_str이 "bbbb"의 경우 

    my_str_list = ["b", "b", "b", "b"]

    set_list = ["b"]
    
    len(set_list) 가 1

"" 처럼 비어있는 문자열인지 확인합니다.

ex) my_str이 ""의 경우 

    my_str_list = []

    set_list = []
    
    len(set_list) 가 0

위의 두 경우가 아니라면 이중 반복문을 돌면서 겹치지 않는 부분 문자열을 추출합니다.

for i in range(len(my_str_list)):
    sub = []
    for j in range(i, len(my_str_list)):
        if my_str_list[j] in sub:
            substring = ''.join(sub)
            substrings.append(len(substring))
            break
        sub.append(my_str_list[j])

        if j == len(my_str_list) - 1:
            substring = ''.join(sub)
            substrings.append(len(substring))

추출하는 방법은 처음 인덱스부터 탐색하며

탐색하고 있는 인덱스의 값이 sub라는 리스트에 존재하지 않을 때에만 sub라는 리스트에 문자를 append하고

만약 탐색하고 있는 인덱스의 값이 sub라는 리스트에 존재할때에는 sub을 문자열로 바꾼 후 

그 문자열의 길이를 substrings 리스트에 append 해줍니다.

 

마지막으로 substrings 중 가장 큰 값을 max( ) 를 통해서 알아내면! 끝!

 

개인적으로 너무 결과가 느리게나와서 다시 한번 풀어보아야 할 것 같습니다.

 

RESULT

THEidEANS/Algorithm_Study