3.Longest Substring Without Repeating Characters

문제 주소

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

Longest Substring Without Repeating Characters - LeetCode

 

문제

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

문제 풀이

string to list//this was int to string(char) list

res = list(map(int, str(num)))

string to list // this is string to string(char) list

a="I love python"
print(list(a))
 
>>['I', ' ', 'l', 'o', 'v', 'e', ' ', 'p', 'y', 't', 'h', 'o', 'n']

Range of Indexes

thislist = ["apple", "banana", "cherry", "orange", "kiwi", "melon", "mango"]
print(thislist[2:5])

i랑 j커서 두고 앞에서 뒤로 훑어가면서 넣는게 좋겠음

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

    input = list(map(int, str(num)))
    temp = []
    longest = 0
    i=0
    j=1

    longest = thislist[i:j]

    while(j<len(input)):
        temp.insert(len(temp), input[i])
        for x in range(len(temp)):
            if(input[i]!=input[j]):
                j++;
                temp.insert(len(temp), input[j])
            else:
                temp = thislist[i:j]
                i=j
                j++
                if(temp>longest):
                    longest = temp
                break;
        i++;

    return longest;

 

처음에는 i를 고정시키고 j만 움직이려고 했는데 곧 그게 잘못되었단걸 알게되었다

왜냐하면 모든 원소가 새 원소 후보랑 같은지 비교해야 했기 때문이다

그래서 while루프 대신에 for 루프를 쓰기로 했다

 

To insert at the end, do this

temp.insert(len(temp), input[i])

Wrong Answer

Runtime: 48 ms

Case 1

Case 2

Case 3

Input

s =

"abcabcbb"

Output

1

Expected

3

output이 맨날 1밖에 안 나오는 이유는 뭐죠

 

temp0 insert : a ['a'] i : 0 0

여기서 끝나버리면 안 되는데

continue → time limit exceed

첫 루프문에서 무슨 일이 일어나고 있는걸까?

 

if→ len(temp) becomes 1 그러나 아무 일도 일어나지 않는다

return indentation may have caused the index ending at 0

그게 문제가 아니었다

 

중첩된 루프문을 벗어나는 방법

breaker = False #our mighty loop exiter!
while True:
    while True:
        if conditionMet:
            #insert code here...
            breaker = True
            break
    if breaker: # the interesting part!
        break   # <--- !

len(input)is 8 so it isn’t a problem

else: at the end is weird, i need to back to while bc i have to change i in that else

 

Runtime Error

AttributeError: 'NoneType' object has no attribute 'insert' temp.insert(0,input[i]) 

 

It’s exactly the else of if(temp==None)

or if temp = [] line ran before this line

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        breaker = False

        for i in range(len(input)):
            if(temp==None):
                temp.insert(0,input[i])
            else:
                for x in range(len(temp)):
                    if(input[i]==temp[x]):
                        if(len(temp)>longest):
                            longest = len(temp)
                        temp = []
                        break;
                        breaker = True
                if breaker:
                    continue;
                temp.insert(0,input[i])
                        

        return longest;

temp = None 으로 초기화하던걸 temp = [] 으로 바꾸니까 저 에러 사라짐

그리고 일단 3 테스트케이스는 통과했다

 

문제 : 인풋이 공백이 되어버리는 문제가 발생

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        breaker = False

        for i in range(len(input)):
            if(temp==None):
                temp.insert(0,input[i])
                if(len(temp)>longest):
                            longest = len(temp)
            else:
                for x in range(len(temp)):
                    if(input[i]==temp[x]):
                        if(len(temp)>longest):
                            longest = len(temp)
                        temp = []
                        break;
                        breaker = True
                if breaker:
                    continue;
                temp.insert(0,input[i])
                        

        return longest;

 

 

해결 : if(temp==None) 을 if(temp==[])로 바꿈

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        breaker = False

        for i in range(len(input)):
            if(temp==[]):
                temp.insert(0,input[i])
                if(len(temp)>longest):
                            longest = len(temp)
            else:
                for x in range(len(temp)):
                    if(input[i]==temp[x]):
                        if(len(temp)>longest):
                            longest = len(temp)
                        temp = []
                        break;
                        breaker = True
                if breaker:
                    continue;
                temp.insert(0,input[i])
                        

        return longest;

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        breaker = False

        for i in range(len(input)):
            if(temp==[]):
                temp.insert(0,input[i])
                if(len(temp)>longest):
                            longest = len(temp)
            else:
                for x in range(len(temp)):
                    if(input[i]==temp[x]):
                        if(len(temp)>longest):
                            longest = len(temp)
                        temp = []
                        break;
                        breaker = True
                if breaker:
                    continue;
                temp.insert(0,input[i])
                        

        return longest;

Wrong Answer

Input

s =

"au"

342 / 987 testcases passed

Output

1

Expected

2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        breaker = False

        for i in range(len(input)):
            if(temp==[]):
                temp.insert(0,input[i])
                longest = len(temp)
            else:
                for x in range(len(temp)):
                    if(input[i]==temp[x]):
                        if(len(temp)>longest):
                            longest = len(temp)
                        temp = []
                        break;
                        breaker = True
                if breaker:
                    continue;
                temp.insert(0,input[i])
                if(len(temp)>longest):
                    longest = len(temp)
                        

        return longest;

longest 두군데에 업뎃 더 넣고 그건 통과했는데

Input

s =

"dvdf"

407 / 987 testcases passed

Output

2

Expected

3

이게 왜 3이죠 vdf라서 3인가봄 근데 temp를 나는 d 만난 순간 버리는데

d만난 순간 temp를 비워버리지 말고 temp에서 d앞의 것을 빼버리는 처리를 해야 할듯함

while 로 커서 옮기듯이 j로 하면 편할 거 같기도

temp 없이 그냥 input만 계속 읽으면서 하면 되니까

while로도 한번 짜자

# Remove Specified Index

---

The `pop()` method removes the specified index.

Remove the second item:

```python
thislist = ["apple", "banana", "cherry"]
thislist.pop(1)
print(thislist)

['apple', 'cherry']

If you do not specify the index, the pop() method removes the last item.

와 꺼내기 졸라귀찮아 for문 또 돌려야될거같으니까 극혐이다 그냥 i j로 가

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        j=0
        breaker = False

        if(len(input)==1):
            return 1;

        while(i<len(input)&j<len(input)):
            if(j-i==0):
                j=j+1
                longest = j-i
            else:
                for x in range(j-i):
                    if(input[j]==input[i+x]):
                        if(j-i>longest):
                            longest = j-i
                        i=i+x
                        j=j+1
                        break;
                        breaker=True
                    if(breaker):
                        continue;
                    j=j+1
                    if(j-i>longest):
                        longest = j-i
        return longest;        

            

                        

        return longest;

여기서 그냥 while(i<len & j<len)을 j<len으로 바꾸니까 제대로 동작하기 시작함 ㅋ

# Definition for singly-linked list.
from ast import List
import math

class Solution:

    
    
    

    def main():

        
        def lengthOfLongestSubstring(s: str) -> int:

            input = list(s)
            temp = []
            longest = 0
            i=0
            j=0
            breaker = False

            print("len(input) : "+str(len(input)))

            if(len(input)==1):
                return 1;

            while(j<len(input)):
                if(j-i==0):
                    j=j+1
                    print("i : "+str(i))
                    print("j : "+str(j))
                    longest = j-i
                    print("longest : "+str(longest))
                else:
                    print("j-i : "+str(j-i))
                    for x in range(j-i):
                        if(input[j]==input[i+x]):
                            print("i : "+str(i))
                            print("j : "+str(j))
                            print("i+x : "+str(i+x))
                            if(j-i>longest):
                                longest = j-i
                                print("longest : "+str(longest))
                            i=i+x
                            print("i : "+str(i))
                            j=j+1
                            print("j : "+str(j))
                            break;
                            breaker=True
                        if(breaker):
                            continue;
                        j=j+1
                        print("i : "+str(i))
                        print("j : "+str(j))
                        if(j-i>longest):
                            longest = j-i
                            print("longest : "+str(longest))
            return longest;        

        print(lengthOfLongestSubstring("abcabcbb"))

    if __name__ == "__main__":
        main()

len(input) : 8 i : 0 j : 1 longest : 1 j-i : 1 i : 0 j : 2 longest : 2 j-i : 2 i : 0 j : 3 longest : 3 i : 0 j : 4 longest : 4 j-i : 4 i : 0 j : 5 longest : 5 i : 0 j : 6 longest : 6 i : 0 j : 7 longest : 7 i : 0 j : 8 longest : 8 8

i가 안 바뀌는데요

거기가 실행이 안 되는 거 같다

# Definition for singly-linked list.
from ast import List
import math

class Solution:

    
    
    

    def main():

        
        def lengthOfLongestSubstring(s: str) -> int:

            input = list(s)
            temp = []
            longest = 0
            i=0
            j=0
            breaker = False

            print("len(input) : "+str(len(input)))

            if(len(input)==1):
                return 1;

            while(j<len(input)):
                if(j-i==0):
                    j=j+1
                    print("i : "+str(i))
                    print("j : "+str(j))
                    longest = j-i
                    print("longest : "+str(longest))
                else:
                    print("j-i : "+str(j-i))
                    for x in range(j-i):
                        print("for x")
                        print("input[j] :"+str(input[j]))
                        print("input[i+x] :"+str(input[i+x]))
                        if(input[j]==input[i+x]):
                            print("j==i+x")
                            if(j-i>longest):
                                longest = j-i
                                print("longest : "+str(longest))
                            i=i+x
                            print("i : "+str(i))
                            j=j+1
                            print("j : "+str(j))
                            break;
                            breaker=True
                        if(breaker):
                            continue;
                        j=j+1
                        print("i : "+str(i))
                        print("j : "+str(j))
                        if(j-i>longest):
                            longest = j-i
                            print("longest : "+str(longest))
            return longest;        

        print(lengthOfLongestSubstring("abcabcbb"))

    if __name__ == "__main__":
        main()

len(input) : 8 i : 0 j : 1 longest : 1 j-i : 1 for x input[j] :b input[i+x] :a i : 0 j : 2 longest : 2 j-i : 2 for x input[j] :c input[i+x] :a i : 0 j : 3 longest : 3 for x input[j] :a input[i+x] :b i : 0 j : 4 longest : 4 j-i : 4 for x input[j] :b input[i+x] :a i : 0 j : 5 longest : 5 for x input[j] :c input[i+x] :b i : 0 j : 6 longest : 6 for x input[j] :b input[i+x] :c i : 0 j : 7 longest : 7 for x input[j] :b input[i+x] :a i : 0 j : 8 longest : 8 8

for문 안에서 j를 add하시면 안됩니다

j놔두고 for문 돌리면서 일치하는거 있는지 비교해주셔야 합니다

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        j=0
        breaker = False

        if(len(input)==1):
            return 1;

        while(j<len(input)):
            if(j-i==0):
                j=j+1
                longest = j-i
            else:
                for x in range(j-i):
                    if(input[j]==input[i+x]):
                        if(j-i>longest):
                            longest = j-i
                        i=i+x
                        j=j+1
                        break;
                        breaker=True
                    if(breaker):
                        continue;
                    
                    if(j-i>longest):
                        longest = j-i
                j=j+1
        return longest;        

            

                        

        return longest;

j==i+x longest : 3 i : 0 j : 4 i : 0 j : 4

if(input[j]==input[i+x]):
                        if(j-i>longest):
                            longest = j-i
                        i=i+x
                        j=j+1

i가 왜 업데이트가 안 됐을까

len(input) : 8 i : 0 j : 1 longest : 1 j-i : 1 for x input[j] :b input[i+x] :a i : 0 j : 1 j-i : 2 for x input[j] :c input[i+x] :a for x input[j] :c input[i+x] :b i : 0 j : 2 longest : 2 j-i : 3 for x input[j] :a input[i+x] :a j==i+x longest : 3 x :0 i : 0 i : 0 i : 0 j : 3 j-i : 4 for x input[j] :b input[i+x] :a for x input[j] :b input[i+x] :b j==i+x longest : 4 x :1 i : 0 i : 1 i : 1 j : 4 j-i : 4 for x input[j] :c input[i+x] :b for x input[j] :c input[i+x] :c j==i+x x :1 i : 1 i : 2 i : 2 j : 5 j-i : 4 for x input[j] :b input[i+x] :c for x input[j] :b input[i+x] :a for x input[j] :b input[i+x] :b j==i+x x :2 i : 2 i : 4 i : 4 j : 6 j-i : 3 for x input[j] :b input[i+x] :b j==i+x x :0 i : 4 i : 4 i : 4 j : 7 4 PS E:\Workspace\Python>

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        j=0
        breaker = False

        if(len(input)==1):
            return 1;

        while(j<len(input)):
            if(j-i==0):
                j=j+1
                longest = j-i
            else:
                for x in range(j-i):
                    if(input[j]==input[i+x]):
                        if(j-i>longest):
                            longest = j-i
                        i=i+x+1
                        break;
                        breaker=True
                    if(breaker):
                        continue;
                if(j-i>longest):
                    longest = j-i
                j=j+1
        return longest;

i=i+x를

i=i+x+1로 바꾸고

j=j+1를 뺌 그 밑에 있는거 그랬더니 됨

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        input = list(s)
        temp = []
        longest = 0
        i=0
        j=0
        breaker = False

        if(len(input)==1):
            return 1;

        while(j<len(input)):
            if(j-i==0):
                j=j+1
                longest = j-i
            else:
                for x in range(j-i):
                    if(input[j]==input[i+x]):
                        if(j-i>longest):
                            longest = j-i
                        i=i+x+1
                        break;
                        breaker=True
                    if(breaker):
                        continue;
                if(j-i>longest)
                    longest = j-i
                j=j+1
        return longest;

여기서

if(j-i>longest)
	longest = j-i
j=j+1

을

j=j+1
if(j-i>longest)
    longest = j-i

으로 바꿨더니 됨 ㅋㅋ 순서는 항상 중요하다.