gistfile1.txt

import Foundation

struct Range: Hashable {
    let start: Int
    let end: Int
    
    var count: Int {
        return (end - start) + 1
    }
    
    var isEven: Bool {
        return count % 2 == 0
    }
    
    var midIndex: Int {
        return start + ((end - start) / 2)
    }
}


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)])
    }
    
    func from(range: Range) -> String {
        return self.str(s: range.start, e: range.end)
    }
}




//func simple(s: String) {
//    var largest = ""
//
//    for i in 0..<s.count {
//        for j in i..<s.count {
//
//            let str = s.str(s: i, e: j)
//            if str == String(str.reversed()) {
//                if str.count > largest.count {
//                    largest = str
//                }
//            }
//
//        }
//    }
//
//    print(largest)
//}

//simple(s: input)

let input = "123xooxp"

class Solution {
    
    var perf = 0
    
    var hitCache = 0
    
    func longestPalindrome(_ s: String) -> String {
        
        if s.isEmpty { return "" }
        
        var cache = [Range: Bool]()
        
        func binarySearchNext(end: Int) -> Int {
            
            var start = 0
            var end = end
            
            var mid = 0
            
            while true {
                
                mid = start + (end - start) / 2
                
                if mid == end || mid == start {
                    break
                }
                
                if let cached = cache[Range(start: mid, end: end)], cached == true {
                    
                    start = start + (mid - start) / 2
                    
                } else {
                    
                    start = mid + (end - mid) / 2
                }
            }
            
            return mid
        }
        
        func longest(range: Range) -> Bool {
            
            perf += 1
            
            if range.count <= 1 {
                return true
            }
            
            print(s.from(range: range))
            
            if let cached = cache[range] {
                hitCache += 1
                return cached
            }
            
            let rightChar = s.safeStr(i: range.end)
            let leftChar = s.safeStr(i: range.start)
            
            if rightChar == leftChar {
                
                let longestHere = longest(range: Range(start: range.start + 1, end: range.end - 1))
                
                if longestHere {
                    
                    cache[range] = true
                    return true
                }
            }
            
            if range.count == 2 {
                return false
            } else if range.count == 3 {
                longest(range: Range(start: 1, end: 2))
            } else {
                let nextStart = binarySearchNext(end: range.end - 1)
                let longestHere = longest(range: Range(start: nextStart, end: range.end - 1))
            }
            
            cache[range] = false
            return false
        }
        
        func getLargestRange() -> Range {
            var largestRange: Range = Range(start: 0, end: 0)
            for c in cache { if c.value && c.key.count > largestRange.count { largestRange = c.key } }
            return largestRange
        }
        
        for i in 0..<s.count {
            let range = Range(start: 0, end: i)
            longest(range: range)
        }
        
        let final =  s.from(range: getLargestRange())
        return final
    }
}

let s = Solution()

let r = s.longestPalindrome(input)
print(r)
print("perf: \(s.perf)")
print("hit cache: \(s.hitCache)")