Algorithm - the longest of non-duplicate word

문제

String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.

str: 텍스트
return: 중복되지 않은 알파벳 길이 (숫자 반환)

예를 들어,

str = "abcabcabc"
return 은 3
=> 'abc' 가 제일 길기 때문

str = "aaaaa"
return 은 1
=> 'a' 가 제일 길기 때문

str = "sttrg"
return 은 3
=> 'trg' 가 제일 길기 때문

처음에 풀었던 방법은

def get_len_of_str(s) :
  temp = []
  temp2 = []
  result= []
  for i in s :
    temp.append(i)
  
  for i in reversed(range(len(temp))) :
    if temp[i] in temp2 :
      result.append(len(temp2))
      temp2 = []
      temp2.append(temp.pop())
      continue
    temp2.append(temp.pop())
  result.append(len(temp2))
 

  return max(result)

입력 받은 string을 for 문을 사용해 먼저 리스트를 만들었다.
pop을 사용해서 문제를 풀기위해 !
(하지만 python에서는 string은 iterable 이기 때문에 굳이 리스트 형식에 안넣어도 될거 같다.)

1. 리스트에 사용할수 있는 함수 pop()를 사용해서 뒤에서 부터 문자를 하나씩 빼와 새로운 temp2 리스트에 넣어준다.

2. if 조건에서는 temp2리스트 안에 temp에서 pop()해온 문자가 존재하면 result에 len(temp2)값을 넣고 temp2를 초기화 시키며 그 중복문자를 temp.append() 한다.

이럼으로써 중복없는 최대길이의 문자를 구할수 있다. 하지만 memory inefficient 면에서 효율적이지 못한 코드인것 같고 클린코드 같지 않아 보인다.

다른 방법으로는

def get_len_of_str(s):
    if len(s) < 2:
        return len(s)    
    
    long_len = 0
    start_idx = 0
    end_idx = 1
    
    while end_idx <= len(s):
        if len(s[start_idx:end_idx]) > long_len:
            long_len = len(s[start_idx:end_idx])
        
        if end_idx < len(s) and s[end_idx] in s[start_idx:end_idx]:
            start_idx = start_idx + 1
            end_idx = start_idx
            
        end_idx += 1
    
    return long_len

1. 문자열의 index를 고려해서 차례차례 비교해 가는 것이다.

2. while문으로 len(s) 끝까지 읽을때 까지 돌린다.

3. while문 안에 첫번째 if로 새로운 long_len이 나올때 값을 바꿔준다. 이로써 내가 이전에 풀었던 방법과 달리 필요없는 메모리를 사용하지 않아도 된다.

4. 두번째 if 문에서 내가 지정한 범위내에서 중복문자가 있을때
   start_idx에 +1을 더해주며 새로운 문자열을 만들어 다시 차례차례 나아간다.

두번째 방법이 이전의 방법보다 메모리 면에서 더 효율적이며 더 깔끔한 코드처럼 느껴진다.

알고리즘 문제를 풀때 어떻게 풀어야 잘 푼 것이고 어떤 방법들이 더 있나 고민해보는 것이 좋을 것 같다.