gistfile1.txt

import Foundation

extension String {
    func safeStr(i: Int) -> String {
        guard i >= 0 && i < self.count else {
            fatalError()
        }
        return String(self[self.index(self.startIndex, offsetBy: i)])
    }
    func safeChar(i: Int) -> Character {
        guard i >= 0 && i < self.count else { fatalError() }
        return self[self.index(self.startIndex, offsetBy: i)]
    }
    func str(s: Int, e: Int) -> String {
        guard s >= 0 && s < self.count else { fatalError() }
        guard s <= e else { fatalError() }
        return String(self[index(startIndex, offsetBy: s)...index(startIndex, offsetBy: e)])
    }
}

typealias Palindrome = [String]
typealias CachedPalindromes = [String?]
typealias PallindromeIndex = Int
typealias Cache = [PallindromeIndex: CachedPalindromes]

class Solution {
    var perf = 0
    
    func longestPalindrome(_ s: String) -> String {
        
        
        var cache = Cache()
        
        var cached1s = Array.init(repeating: "", count: s.count)
        
        s.enumerated().forEach { (arg) in
            let (k, v) = arg
            cached1s[k] = String(v)
        }
        
        cache[1] = cached1s
        
        var key = 1
        
        while true {
            
            key += 1
            
            let isEven = key % 2 == 0
            let isOdd = !isEven
            
            cache[key] = Array.init(repeating: nil, count: s.count)
            
            if isEven {
                
                // EVEN CONCAT
                
                let halfKey = (key / 2)
                let halfPallindromes = cache[halfKey]!
                
                // since we're look to left, we start at key, it will find left by half key
                var startingAt = key + 1
                var endingAt = (s.count - 1) - (halfKey - 1) //remember key is off by 1 from index
                
                if startingAt <= endingAt {
                
                    for i in startingAt...endingAt {
                        guard  let el = halfPallindromes[i] else { continue }
                        if let toLeft = halfPallindromes[i - key] {
                            if toLeft == el {
                                let newValue = toLeft + el
                                cache[key]![i - key] = newValue
                                cache[key]![i + halfKey] = newValue
                            }
                        }
                    }
                }
                
                
                
                // EVEN EXPAND
                let lastEven = key - 2
                startingAt = lastEven
                endingAt  = (s.count) - lastEven
                
                if startingAt <= endingAt {
                    
                    if let twoAgoPallindromes = cache[key - 2] {
                        
                        for i in startingAt...endingAt {
                            guard let el = twoAgoPallindromes[i] else { continue }
                            
                            let toLeft = s.safeStr(i: i - 1)
                            let toRight = s.safeStr(i: i + key + 1)
                            
                            if toLeft == toRight {
                                cache[key]![i - 1] = toLeft + el + toRight
                                cache[key]![i - key] = toLeft + el + toRight
                            }
                        }
                    }
                }
                
                
            }
            
            
            if isOdd {
               
                // ODD MERGE
                
                let halfKey = (key / 2) + 1
                guard halfKey > 0 else { fatalError() }
                let halfPallindromes = cache[halfKey]!
                var startingAt = halfKey - 1
                var endingAt = s.count - halfKey
                
                
                // TODO: need this?
                //                if startingAt > endingAt {
                //                    endingAt = 0
                //                    startingAt = 0
                //                }
                
                for i in startingAt...endingAt {
                    guard i - 1 >= 0 && i + 1 < s.count else { fatalError() }
                    
                    if
                        let leftMerge = halfPallindromes[i - 1],
                        let rightMerge = halfPallindromes[i + 1] {
                        
                        if leftMerge == rightMerge {
                            let merged = String(leftMerge.dropLast()) + rightMerge
                            cache[key]![i - (halfKey - 1)] = merged
                            cache[key]![i + (halfKey - 1)] = merged
                        }
                    }
                }
                
                // ODD EXPAND
                
                // no worry about 1's. (no-op)
                let twoAgoKey = key - 2
                let twoAgoPallindromes = cache[twoAgoKey]!
                
                // we're expanding out 1 so contract insets
                startingAt = twoAgoKey
                endingAt = (s.count - twoAgoKey) - 1
                

                // TODO: need this?
//                if startingAt > endingAt {
//                    endingAt = 0
//                    startingAt = 0
//                }
                
                for i in startingAt...endingAt {
                    guard let el = twoAgoPallindromes[i] else { continue }
                    
                    let toLeft = s.safeStr(i: i - twoAgoKey)
                    let toRight = s.safeStr(i: i + twoAgoKey)
                    
                    if toLeft == toRight {
                        cache[key]![i] = toLeft + el + toRight
                    }
                }
            }
            
            
            
            if key == s.count { break }
        }
        
        
        for i in (0...s.count).reversed()   {
            let ps = cache[i]!
            
            for p in ps {
                
                if p != nil {
                    return p!
                }
            }
        }
        
        
        
        

        fatalError() // HAHAH
    }
}





let s = Solution()
//let r = s.longestPalindrome(input)
//print("answer \(r) in \(s.perf) steps")
//
func assertCompletePallindrome(_ p: String) {
    assert(Solution().longestPalindrome(p) == p)
}



let bigInput2 = "XOOX"


let r2 = s.longestPalindrome(bigInput2)
print(s.perf)
print(r2)





//
//assert(Solution().longestPalindrome("321123211232112") == "21123211232112")
//assert(Solution().longestPalindrome("44444444444444443333333334444444444444444") == "44444444444444443333333334444444444444444")

//assertCompletePallindrome("4333333334")
//assert(Solution().longestPalindrome("3210123210012321001232100123210123") == "3210123210012321001232100123210123")
//assert(Solution().longestPalindrome("aba") == "aba")
//assert(Solution().longestPalindrome("abcde") == "a")
//assert(Solution().longestPalindrome("aaabbbaaa") == "aaabbbaaa")
//assert(Solution().longestPalindrome("FaaabbbaaaG") == "aaabbbaaa")
//assert(Solution().longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") == "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
//assert(Solution().longestPalindrome("eabcb") == "bcb")
//assert(Solution().longestPalindrome("ac") == "a")
//
//
//assert(Solution().longestPalindrome("bbb") == "bbb")
//assert(Solution().longestPalindrome("bbbbb") == "bbbbb")
//assert(Solution().longestPalindrome("bbbb") == "bbbb")
//assert(Solution().longestPalindrome("bbbbbb") == "bbbbbb")
//
//assert(Solution().longestPalindrome("aaabbbbaaa") == "aaabbbbaaa")
//
//
//assertCompletePallindrome("aaaaaaaaaaaaaa")
//
//assertCompletePallindrome("aabbaabbaabbaabbaa")
//assertCompletePallindrome("")
//
//assert(Solution().longestPalindrome("a") == "a")
//assert(Solution().longestPalindrome("aa") == "aa")
////
////
//let bigInput = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123"
//let bigExpectation = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123"
//
//
//
//let r2 = s.longestPalindrome(bigInput)
////
//print("input")
//print(bigInput)
////
//print("my result")
//print(r2)
////
//print("expected")
//print(bigExpectation)
////
////print(r.count)
////print(bigExpectation.count)
////
//assert(r2 == bigExpectation)
//
//