본 문서는 leetcode(https://leetcode.com/problems/longest-substring-without-repeating-characters)를 기준으로 작성하였습니다.

Longest Substring

문제

주어진 string(s)에서 중복된 문자가 없는 가장 긴 subString의 길이를 반환하시오.

규칙

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

문제 풀이 아이디어 생각해보기

two pointer를 떠올렸다. left와 right가 오른쪽으로 한칸씩 움직인다. 이때 right에 해당하는 문자를 객체에 기록하며 카운팅한다. 만약 right가 1보다 커진다면 중복된 문자가 있는 것으로 간주하여 left에 해당하는 문자를 객체에서 지우고 오른쪽으로 한칸씩 이동시킨다. 이 과정은 right가 s.length에 도달할 때 까지 반복한다.

풀이

1. 문자를 카운팅할 객체를 선언하고 중복된 문자가 있는지 확인하는 함수를 정의한다.

코드

let numberOfCharsForCounting = {};
    
const isNotRepeatingChar = () => {
  for (const value of Object.values(numberOfCharsForCounting)) {
    if (value > 1) {
      return false;
    }
  }

  return true;
}

2. 두 개의 pointer를 선언하고, 위의 논리대로 코드를 작성하였다.

let longestLength = 0;
let left = 0;
let right = 0;

while (right <= s.length) {
  if (isNotRepeatingChar()) {
    longestLength = Math.max(longestLength, Object.values(numberOfCharsForCounting).length);
    
    const char = s[right++];
    numberOfCharsForCounting[char] = numberOfCharsForCounting[char] + 1 || 1;
  } 
  else {
    const char = s[left++];
    numberOfCharsForCounting[char] -= 1;
    
    if (numberOfCharsForCounting[char] === 0) {
      delete numberOfCharsForCounting[char]
    }
  }
}

return longestLength;

다른 사람의 접근법

나름 정직하고 깔끔하게 작성해서 좋은 점수를 받을 것으로 생각했으나, 성능 랭킹을 확인해보니 하위권에 속했다. 상위권에 속하는 다른 사람의 풀이를 참고해 보았다.

원리는 간단했다. 객체를 사용하는 대신 right 포인터에 해당하는 문자를 배열에 삽입한다. 그리고 indexOf를 사용해 존재하는 문자라면 splice로 해당하는 부분까지 잘라낸다. 포인터가 이동하는 반복문, 검증하는 반복문으로 같은 2중 for문에 속하지만 이 코드가 약 10배가 빠르다.

아무래도 2중 포문을 돌면 중복되는 문자가 없어질 때 까지 계속 검증하는 코스트가 필요하다. 그리고 1중 포문을 돌려가며 객체가 가진 문자 수를 지워주어야 한다. 하지만 후자의 경우는 splice를 사용해 같은 1중 포문일지라도 중복되는 캐릭터가 있는지 검증하는 코스트를 생략할 수 있다.

여기서 성능의 차이가 발생했을 것으로 추측한다.

수정 후 최종 코드

let subString = [];

let longestLength = 0;
let right = 0;

while (right < s.length) {
  const charIndexInSubString = subString.indexOf(s[right]);
  
  if (charIndexInSubString === -1) {
    subString.push(s[right]);
    longestLength = Math.max(longestLength, subString.length);
  } else {
    subString.push(s[right]);
    subString.splice(0, subString.indexOf(s[right]) + 1);
  }

  right++;
}

return longestLength;