[Algorithm] 가장 긴 펠린드롬

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12904

💬 Idea

• 가장 긴 펠린드롬의 길이를 구하는 문제이므로 가장 큰 개수 (s의 count)부터 -1씩 내려가면서 최고 길이를 구한다.
• j : 시작점
• p : 중간 인덱스
• l : 끝 인덱스
• j부터 p까지 돌면서 양 끝 인덱스를 비교하고, 비교군은 k씩 좁혀간다.
  • abba
    • 4인 펠린드롬을 구할 때 → a와 a 비교 (0, 3) // b와 b 비교 (1, 2)
    • 3인 펠린드롬을 구할 때
      • abb → a와 b 비교
      • bba → b와 a 비교

💬 풀이

import Foundation

func solution(_ s:String) -> Int {
    var maxSubstring = 1
    var s = Array(s)
    
    if s.count == 0 { return 0 }
    if s.count == 1 { return 1 }
    
    for i in stride(from: s.count, to: 1, by: -1) {
        var isPal = false
        
        ol: for j in 0...s.count - i {
            var p = (i / 2) + j
            var l = j + i - 1
            
            for k in j...p {
                if s[k] != s[l - (k - j)] {
                    continue ol
                }
            }
            
            return i
        }
    }
    
    return maxSubstring
}