C#으로 반복 문자 없는 가장 긴 부분 문자열의 길이 찾는 방법

개요

문자열 알고리즘 문제 중 가장 대표적인 유형 중 하나가 바로 "중복 문자가 없는 가장 긴 부분 문자열" 문제입니다. 이 문제는 주어진 문자열에서 같은 문자가 반복되지 않는 가장 긴 연속 부분 문자열의 길이를 구하는 것이 목표입니다.

이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 사용하면 O(N)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 두 개의 포인터 i와 j를 활용하며, 처음에는 두 포인터 모두 문자열의 같은 위치를 가리킵니다. 문자열을 순회하면서 문자를 리스트에 추가하고, 중복 문자가 발견되면 윈도우 왼쪽 끝(i)의 문자를 제거하는 방식으로 진행됩니다.

알고리즘 동작 방식

1. 두 포인터 iPointer와 jPointer를 선언하고 0으로 초기화합니다.
2. jPointer가 가리키는 문자가 이미 리스트에 존재하면, iPointer가 가리키는 문자를 리스트에서 제거하고 iPointer를 1 증가시킵니다.
3. 존재하지 않으면 해당 문자를 리스트에 추가하고 jPointer를 1 증가시킨 뒤, 현재 리스트의 개수와 기존 최대값 중 더 큰 값을 max에 저장합니다.
4. jPointer가 문자열의 끝에 도달할 때까지 위 과정을 반복합니다.

예제 1

입력 — s = "abcabcbb"

출력 — 3

설명 — 정답은 "abc"이며, 길이는 3입니다.

예제 2

입력 — s = "bbbbb"

출력 — 1

설명 — 정답은 "b"이며, 길이는 1입니다.

시간 복잡도 — O(N)

공간 복잡도 — O(N)

C# 구현 예제

using System;
using System.Collections.Generic;

public class Arrays {
    public int LongestSubstringWithNoRepeatingCharacters(string s) {
        List<char> c = new List<char>();
        int iPointer = 0;
        int jPointer = 0;
        int max = 0;
        while (jPointer < s.Length) {
            if (c.Contains(s[jPointer])) {
                c.Remove(s[iPointer]);
                iPointer++;
            } else {
                c.Add(s[jPointer]);
                jPointer++;
                max = Math.Max(c.Count, max);
            }
        }
        return max;
    }
}

class Program {
    static void Main(string[] args) {
        Arrays arr = new Arrays();
        int res = arr.LongestSubstringWithNoRepeatingCharacters("abcabcbb");
        Console.WriteLine(res);
    }
}

실행 결과

3

마무리

슬라이딩 윈도우 기법은 문자열 처리 문제에서 매우 유용하게 활용되는 패턴입니다. 추가로 List 대신 HashSet을 사용하면 Contains 검사를 O(1)로 수행할 수 있어 전체 성능을 더욱 향상시킬 수 있습니다.