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


class Solution {
    var perf = 0
    
    func longestPalindrome(_ s: String) -> String {
        
        var cache = s.map { _ in 1 } { didSet {
//            print(cache)
            } }
        
        var largest = (0, 0)
        
        for i in 0..<s.count {
            
            let leftIndex = i - 1
            let twoLeftIndex = i - 2
            
            // start 2 inset.  for pallindromes of size 1 or 2, special case it
            guard leftIndex >= 0 && twoLeftIndex >= 0 else { continue }
            
            let thisChar = s.safeStr(i: i)
            let leftChar = s.safeStr(i: leftIndex)
            let twoLeftChar = s.safeStr(i: twoLeftIndex)

            if thisChar == leftChar {
                cache[i].append(2)
            }
            
            if thisChar == twoLeftChar {
                cache[i].append(3)
            }
            
            for j in cache[i - 1] {
                
                perf += 1
                
                let beforeCacheIndex = i - j - 1
                
                if beforeCacheIndex < 0 {
                    continue
                }
                
                let beforeCacheChar = s.safeStr(i: beforeCacheIndex)
                
                if thisChar == beforeCacheChar {
                    cache[i].append(j + 2)
                }
                
                if j + 2 > largest.1 {
                    largest = (i - (j + 2) + 1, i)
                }
            }
        }
        
        print(largest)
        
        let ps = s.str(s: largest.0, e: largest.1)
        
        return ps

        
    }
}



func assertCompletePallindrome(_ p: String) {
    assert(Solution().longestPalindrome(p) == p)
}

//assertCompletePallindrome(input)

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

//print(r)

print(s.perf)

//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)
//
//