📋 중복되지 않는 가장 긴 문자열

문제

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

예를 들어,
str = "abcabcabc"
return 은 3
=> 'abc' 가 제일 길기 때문

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

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

---

📌 1. 나의 풀이

const getLengthOfStr = str => {
  if (str.length === 0) return 0;
  let arr = [];
  for (let i = 0; i < str.length; i++) {
    for (let j = i; j < str.length; j++) {
      if (i === j) arr.push([])
      else if (arr[i].includes(str[j])) break;
      arr[i].push(str[j])
    }
  }

  return Math.max(...arr.map((e) => e.length));
}

사실 그렇게 효율적인 방법처럼 보이지는 않는다.

나는 빈 배열을 변수로 선언하고, 중첩루프를 돌린 뒤 j루프의 초기값은 i로 설정해주었다.
그리고 만약 i와 j값이 같다면 arr에 빈 배열을 하나 넣어준 후, 겹치는 값이 없다면 arr에 있는 빈 배열에 값을 넣어주는 루프를 만들었다.

예를들어 str로 "abcabcd"를 넣었다면 arr의 결과는 다음과 같다.

0: (3) ['a', 'b', 'c']
1: (3) ['b', 'c', 'a']
2: (3) ['c', 'a', 'b']
3: (4) ['a', 'b', 'c', 'd']
4: (3) ['b', 'c', 'd']
5: (2) ['c', 'd']
6: ['d']

이제 return Math.max(...arr.map((e) => e.length));를 통해 이중 가장 많은 값을 가진 배열의 length를 반환하면 되는것이다.

하지만 오늘 팀원분과 함께 얘기하던 중, 색다른 방법을 소개받았다.
그 방법은 내 풀이보다 훨씬 효율적이였다.

---

📌 2. 모범 답안

const getLengthOfStr = str => {
  let topLength = 0;
  let arr = [];

  for (i = 0; i < str.length; i++) {
    if (arr.indexOf(str[i]) == -1) {
      arr.push(str[i]);
    } else {
      arr = arr.slice(arr.indexOf(str[i]) + 1);
      arr.push(str[i]);
    }
    if (topLength < arr.length) {
      topLength = arr.length;
    }
  }

  return topLength;
};

이 방법은 arr에 겹치는 문자열이 없다면 arr에 넣고, 만약 겹치는 문자열이 있다면, slice를 통해 앞에서부터 그 겹치는 문자열까지를 잘라낸다.
그와 동시에 arr.length가 가장 길어질 때 마다 topLength 변수에 저장한다.

이를 반복하고, 루프가 끝나면 가장 길었던 배열의 길이인 topLength를 반환한다.

중첩루프를 돌리지 않아 내가 작성한 코드보다 시간복잡도도 훨씬 좋고 가독성도 좋다.