JavaScript로 서로 다른 두 문자만 포함하는 가장 긴 부분 문자열 찾기

문제 이해하기

문자열을 인수로 받아, 원본 문자열에서 일부 문자를 삭제한 뒤 서로 다른 문자를 최대 2개까지만 포함하는 가장 긴 문자열을 만드는 JavaScript 함수를 작성해 보겠습니다. 함수는 최종적으로 해당 문자열의 길이를 반환해야 합니다.

예를 들어 입력 문자열이 다음과 같다고 가정해 봅시다.

const str = 'kjeljsdl';

이때 기대되는 출력 결과는 다음과 같습니다.

const output = 4;

'k', 'e', 's', 'd' 네 문자를 제거하면 'j'와 'l' 두 종류의 문자로만 이루어진 'jljl'이라는 부분 문자열을 얻을 수 있습니다. 이것이 조건을 충족하는 가장 긴 문자열이기 때문에 결과는 4가 됩니다.

접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

• Set 객체를 이용해 문자열에 등장하는 고유한 문자들을 추출합니다.
• 추출된 문자들로 만들 수 있는 모든 두 문자 조합을 생성합니다.
• 각 조합마다 원본 문자열을 순회하며 해당 조합에 포함된 문자만 남긴 부분 문자열의 길이를 계산합니다.
• 계산된 길이 중 가장 큰 값을 결과로 반환합니다.

예제 코드

const str = 'kjeljsdl';
const longestSubstring = (str = '') => {
   const { length } = str;
   if (length <= 1){
      return 0;
   };
   const keys = [...new Set(str)];
   const arr = [];
   let max = 0;
   for (let i = 0; i < keys.length - 1; i++) {
      for (let j = i + 1; j < keys.length; j++) {
         arr.push(keys[i] + keys[j]);
      }
   }
   arr.forEach(item => {
      let sub = '';
      for (let i = 0; i < str.length; i++) {
         if (sub[sub.length - 1] === str[i]) {
            sub = '';
            break;
         }
         if (item.includes(str[i])) {
            sub += str[i];
         }
      }
      if (sub && sub.length > max){
         max = sub.length;
      };
   });
   return max;
}
console.log(longestSubstring(str));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

4

코드 동작 원리

1. [...new Set(str)]을 사용해 문자열에서 중복을 제거한 고유 문자 배열을 만듭니다. 예제 문자열의 경우 ['k', 'j', 'e', 'l', 's', 'd']가 됩니다.
2. 중첩 반복문을 통해 서로 다른 두 문자로 만들 수 있는 모든 조합을 배열에 담습니다.
3. 각 조합에 대해 원본 문자열을 처음부터 끝까지 순회하면서, 조합에 속한 문자만 순서대로 새 문자열에 추가합니다.
4. 직전에 추가한 문자와 같은 문자가 연속으로 나타나면 해당 조합은 유효하지 않은 것으로 처리하고 다음 조합으로 넘어갑니다.
5. 모든 조합을 검사한 뒤 가장 긴 부분 문자열의 길이를 반환합니다.

이 방식의 시간 복잡도는 고유 문자의 개수를 n, 문자열의 길이를 m이라 할 때 대략 O(n² × m)입니다. 따라서 문자열이 매우 길거나 고유 문자가 많은 경우에는 슬라이딩 윈도우 기법을 활용하면 O(m) 시간 안에 문제를 해결할 수 있어 더욱 효율적입니다.