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 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)])
    }
}

let input = "xoxoxoxoxoxoxoxox"


class Solution {
    
    var perf = 0
    
    func longestPalindrome(_ s: String) -> String {
//
        var ranges: [Int: (Int, Int)] = {

            var c = [Int: (Int, Int)]()

            s.enumerated().forEach { foo in
                c[foo.offset] = (foo.offset, foo.offset)
            }

            return c
        }()
//        { didSet { print("ranges \(ranges)") } }
        
      
        
        var pallindromes =  [String: [Int]]()
//        { didSet { print("pallindromes: \(pallindromes)") } }
        
        
        
        func updatePallindromes(str: String, middle: Int) {
            
            if var currrentPs = pallindromes[str] {
                currrentPs.append(middle)
                pallindromes[str] = currrentPs
            } else {
                pallindromes[str] = [middle]
            }
        }
        
        
        // init pallindromes
        
        s.enumerated().forEach {
            updatePallindromes(str: String($0.element), middle: $0.offset)
        }
        
        func updateRange(key: Int, range: (Int, Int)) {
            ranges[key] = range
            updatePallindromes(str: s.str(s: range.0, e: range.1), middle: key)
        }
        
        var updatedRange = false
        
        
        func updateRange(key: Int) {
            
            perf += 1
            
            guard let currentRange = ranges[key] else { fatalError() }
            
            let leftIndex = currentRange.0 - 1
            let rightIndex = currentRange.1 + 1
            
            // reached edge
            if leftIndex == 0 || rightIndex == s.count - 1 {
                
                if s.safeStr(i: leftIndex) == s.safeStr(i: rightIndex) {
                    updateRange(key: key, range: (leftIndex, rightIndex))
                }
   
                updatedRange = true
                
            } else if leftIndex > 0 && rightIndex < s.count - 1 {  // still expanding
                
                guard let leftRange = ranges[leftIndex] else { fatalError("this should always exist") }
                guard let ps = pallindromes[s.str(s: leftRange.0, e: leftRange.1)] else { return }
                
                if ps.contains(rightIndex) {
                    let halfRange = (leftRange.1 - leftRange.0) / 2
                    let newRange = (leftRange.0, rightIndex + halfRange)
                    updateRange(key: key, range: newRange)
                    
                    updatedRange = true
                }
                
            }
        }
        
    
        while true {
            
            updatedRange = false
            
            for r in ranges.keys {
                updateRange(key: r)
            }
            
            if !updatedRange {
                break
            }
        }
        
        let longest =  pallindromes.max(by: { (kv1, kv2) -> Bool in
            return kv2.key.count > kv1.key.count
        })
        
        return longest?.key ?? ""
    }
}
//
//func assertCompletePallindrome(_ p: String) {
//    assert(Solution().longestPalindrome(p) == p)
//}
//
//assertCompletePallindrome(input)

let s = Solution()
//let r = s.longestPalindrome("XOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOOXOOO")
let r = s.longestPalindrome(input)

print(s.perf)

print(r)
0
assert(r == input)



//assertCompletePallindrome("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA")

//print("foo")

//assertCompletePallindrome("aaaa")
//assertCompletePallindrome("aaaaaaaa")
//
//
//assertCompletePallindrome("4333334")
//
////
//assert(Solution().longestPalindrome("321123211232112") == "21123211232112")
//
//assert(Solution().longestPalindrome("auieo") == "a")
//assert(Solution().longestPalindrome("a") == "a")
//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("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 input = "XOXOOXOXXOXOOXOXXOXOOXOXXOXOOXOXYXOXOOXOXXOXOOXOXXOXOOXOXXOXOOXOX"
//
//let s = Solution()
//let r = s.longestPalindrome(input)
//
////print("answer \(r) in \(s.perf) steps")

//
//let bigInput = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123"
//let bigExpectation = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123"

//
//
//let s = Solution()
//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)

//print(s.perf)
//
//