[Swift] Swift로 중복문자가 없는 가장 긴 부분 문자열 찾기

문제 설명

주어진 문자열에서 중복된 문자가 없는 가장 긴 서브스트링을 찾아야 합니다. 또한, 해당 서브스트링의 길이도 함께 출력해야 합니다.

예제

입력 : "aabcbbc"
출력 : 3 // "abc"

입력 : "bbbbbb"
출력 : 1 // "b"

입력 : "aaaaabbbcedfg"
출력 : 6 // "bcedfg"

해결 방법

이 문제를 해결하기 위해 슬라이딩 윈도우(Sliding Window) 기법과 해시셋(Hash Set) 을 사용합니다.

• 슬라이딩 윈도우: 문자열을 순회하면서, 현재 서브스트링의 길이를 유지하면서 중복 문자가 나오면 윈도우의 시작을 조정합니다.
• 해시셋: 현재 윈도우에서 중복 문자가 존재하는지 빠르게 확인하기 위해 사용합니다.

이제 Swift 코드로 구현해보겠습니다.

Swift 코드 구현

import Foundation

func longestUniqueSubstring(_ s: String) -> (length: Int, substring: String) {
    var charSet = Set<Character>()
    var left = 0
    var maxLength = 0
    var startIndex = 0
    let chars = Array(s)
    
    for right in 0..<chars.count {
        while charSet.contains(chars[right]) {
            charSet.remove(chars[left])
            left += 1
        }
        
        charSet.insert(chars[right])
        
        if right - left + 1 > maxLength {
            maxLength = right - left + 1
            startIndex = left
        }
    }
    
    let longestSubstring = String(chars[startIndex..<(startIndex + maxLength)])
    return (maxLength, longestSubstring)
}

// 테스트 예제
let testCases = ["aabcbcbc", "aaaaaaa", "abbbcedd"]
for testCase in testCases {
    let result = longestUniqueSubstring(testCase)
    print("Input: \(testCase) -> Output: \(result.length) // \(result.substring)")
}

실행 결과

예제처럼 출력된 것을 확인할 수 있다.

코드 설명

1. charSet 사용: 현재 윈도우 내에 존재하는 문자를 저장하여 중복을 확인합니다.
2. 슬라이딩 윈도우: left는 윈도우의 시작 위치, right는 윈도우의 끝 위치입니다.
3. 중복 문자 처리:
   • charSet에 이미 문자가 존재하면 left를 이동하여 중복을 제거합니다.
   • charSet에 문자가 없다면 추가합니다.
4. 최대 길이 갱신: 현재 윈도우의 길이가 기존 maxLength보다 크면 값을 업데이트합니다.

시간 복잡도 분석

• 각 문자는 right 포인터에 의해 한 번 탐색되고, left 포인터에 의해 한 번 제거됩니다.
• 따라서 시간 복잡도는 O(n) 입니다.