🧨 문제

어떤 문자열에서, 연속적으로 이어진 부분문자열 중,
중복되지 않은 알파벳으로 이루어진 문자열의 길이의 최댓값을 반환하는 함수를 만들어라

ex1)
str="abcabcabc" 일때 'abc' 3 반환

ex2)
str=aaaaaa 일때 'a' 1 반환

ex3)
str=sttrg 일때,
중복 되지않은 문자열은'st' 'trg' 인데,
가장 길이가 긴 것은 'trg'임으로 3 반환

💥 (!잘못된!) 내 풀이

def get_len_of_str(s):
    result=int(0)
    cnt=int(0)
    letters=str()

    for i in range(len(s)):
      if s[i] not in letters:
        letters+=s[i]
        cnt+=1
        
        if result < cnt:
          result=cnt
      else:
        letters=s[i]
        cnt=1
    
    return result

📍 step 1

def get_len_of_str(s):
   result=int(0) # 최댓값을 담을 변수
   cnt=int(0) # 문자열의 길이를 세는 변수
   letters=str() # 중복되지 않은 문자열을 담는 변수

필요한 변수 생성

📍 step 2

   for i in range(len(s)):
     if s[i] not in letters:
       letters+=s[i]
       cnt+=1
       
     else:
       letters=s[i]
       cnt=1
   
   return result

for 문을 순회 하면서,
letters에 중복되지 않는 문자열을 담으며,
cnt로 그 문자열의 길이를 센다.

만약 중복이 발생하면, letters를 중복이 발생한 알파벳으로 cnt를 1로 초기화 시킨다.

📍 step 3

   for i in range(len(s)):
     if s[i] not in letters:
       letters+=s[i]
       cnt+=1
       
     	if result < cnt:
           result=cnt
         
     else:
       letters=s[i]
       cnt=1
   
   return result

중복이 발생하게 되면, cnt값이 초기화 되기 때문에,
그 전에 발생한 가장 큰 cnt를 result에 저장하고 최종적으로 저장된 result를 반환한다.

🚩 문제점!!

내 풀이의 경우 가장 첫째 문자를 기준으로, 발생한 중복되지 않은 가장 긴 문자열을 반환하지만, 가장 긴 문자열이 중간에 끼어 있을 경우 잘못된 값을 반환하게 된다.

ex)
str ='abcdaxyz' 일때,
가장 긴 문자열은 7('bcdaxyz')인데,
4를 ('abcd')반환 한다.

✨ 개선 풀이 1

def get_len_of_str(s):
#step 1
   result=int(0)
   cnt=int(0)
   letters=str()
   
#step 2
   for i in range(len(s)):
     if s[i] not in letters:
       letters+=s[i]
       print(letters)
       cnt+=1
       if result < cnt:
         result=cnt
         
#step 3
     else:
       if letters[0]==s[i]:
         letters=letters[1:]+s[i]
         cnt=len(letters)
       elif letters[-1]==s[i]:
         letters=s[i]
         cnt=1
       else:
         letters=letters[letters.index(s[i])+1:]+s[i]
         cnt=len(letters)
         
   
   return result

📍 step 1

def get_len_of_str(s):
   result=int(0) # 최댓값을 담을 변수
   cnt=int(0) # 문자열의 길이를 세는 변수
   letters=str() # 중복되지 않은 문자열을 담는 변수

필요한 변수 생성

📍 step 2

   for i in range(len(s)):
     #중복이 발생 되지 않는 경우
     if s[i] not in letters:
       letters+=s[i]
       print(letters)
       cnt+=1
       if result < cnt:
         result=cnt         

for 문을 순회 하면서,
letters에 중복되지 않는 문자열을 담으며,
cnt로 그 문자열의 길이를 세고,
가장 큰 cnt를 result에 담는다.

만약 중복이 발생하면,
중복이 발생하는 case별로
다르게 처리한다

📍 step 3

  for i in range(len(s)):
     # ... 중략 ...
     
     #중복이 발생 되는 경우
     else: 
       #case 1
       if letters[0]==s[i]:
         letters=letters[1:]+s[i]
         cnt=len(letters)
         
       #case 2
       elif letters[-1]==s[i]:
         letters=s[i]
         cnt=1
       
       #case 3
       else:
         letters=letters[letters.index(s[i])+1:]+s[i]
         cnt=len(letters)
         
   
   return result

중복이 발생하는 경우 크게 3개의 case로 나누어 처리 하고,
최종적으로 결과 result를 반환한다.

📌 case1

중복되는 문자열이 letters의 첫글자 일때,

ex)
str = 'abcda...' ⇒ letters=abcd, s[i]=a

letters='bcda'로 초기화 시킨다.
cnt는 변함 없다.

📌 case2

중복되는 문자열이 letters 끝글자 일때,

ex)
str = 'abcdd...' ⇒ letters=abcd, s[i]=d

letters='d'로 초기화 시킨다.
cnt는 1로 초기화 한다.

📌 case3

중복되는 문자열이 letters 중간에 있을 때,

ex)
str = 'abcdb...' ⇒ letters=abcd, s[i]=b

letters='cdb'로 초기화 시킨다.
cnt는 letters의 길이로 초기화 한다.

✨ 개선 풀이 1-1

def get_len_of_str(s):
# step 1
    result = int(0)
    cnt = int(0)
    letters = str()

# step 2
    for i in range(len(s)):
        if s[i] not in letters:
            letters += s[i]
            print(letters)
            cnt += 1
            if result < cnt:
                result = cnt

# step 3
        else:
            letters = letters[letters.index(s[i])+1:]+s[i]
            cnt = len(letters)

    return result

step1 과 step2는 동일하나
step3에서 굳이 case1~3을 나누지 않고, case3로 모든 경우를 처리 할 수 있다.

🎈 짝 풀이

내 풀이와 아이디어는 같으나, 중복되지 않은 문자열들을 key로, 그 길이를value로 저장하여
가장 큰 value 값을 반환하는 함수를 작성

dictionary를 사용하여 중복되지 않은 문자열을 모두 추적 할 수 있음으로 더 확장 가능한 풀이인 거 같다.