LeetCode in Swift: Longest Palindromic Substring

Problem Statement

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Original LeetCode problem page

My Solution in Swift

An array of palindrome lengths centred at previous locations is used to make my solution run in linear time O(n)

func longestPalindrome<T: Equatable>(s: [T]) -> [T] {
    var sLen = s.count
    var curPalLen = 0
    var palLens: [Int] = []
    var maxPal = (idx: -1, len: -1)
    var i = 0
    var updateMaxPal = { () -> () in
        if curPalLen > maxPal.len {
            maxPal = (palLens.count, curPalLen)
        }
    }
    outer: while i < sLen {
        // find the longest palindrome centered at current center position, i.e. 
        // palLens.count
        if i > curPalLen && s[i] == s[i - curPalLen - 1] {
            ++i
            curPalLen += 2
            continue
        }
        updateMaxPal()
        palLens.append(curPalLen)
        // move to next center
        //
        // we can do this either naively by just moving to next center position 
        // of 2*n + 1 positions one by one:
        //      i = (palLens.count - 1) / 2 + 1
        //      palLen = palLens.count % 2
        //
        // or we could take advantage of the palindrome symmetry:
        //      a b a b a b a b a
        //     0103050709070503010
        //     |
        //     |? ? ? ? ? ? ? ? ?
        //     0??????????????????
        //      |
        //      a|? ? ? ? ? ? ? ?
        //     01?????????????????
        //       |
        //      a|? ? ? ? ? ? ? ?
        //     010????????????????
        //        |
        //      a b a|? ? ? ? ? ?
        //     0103???????????????
        //          |
        //      a b a b a|? ? ? ?
        //     010305?????????????
        //            |
        //      a b a b a b a|? ?
        //     01030507???????????
        //              |
        //      a b a b a b a b a|
        //     0103050709?????????
        let curPalLeftHalfStartIdx = palLens.count - 1 - curPalLen
        let curPalLeftHalfEndIdx = palLens.count - 2
        for var j = curPalLeftHalfEndIdx; j >= curPalLeftHalfStartIdx; --j {
            let distToLeftEdge = j - curPalLeftHalfStartIdx
            if palLens[j] == distToLeftEdge {
                curPalLen = distToLeftEdge
                continue outer
            }
            palLens.append(min(distToLeftEdge, palLens[j]))
        }
        curPalLen = 1
        ++i
    }
    updateMaxPal()
    let startIdx = maxPal.idx / 2 - maxPal.len / 2
    return Array(s[startIdx..<startIdx + maxPal.len])
}

func longestPalindrome<T: Equatable>(s: [T]) -> [T] {

var sLen = s.count

var curPalLen = 0

var palLens: [Int] = []

var maxPal = (idx: -1, len: -1)

var i = 0

var updateMaxPal = { () -> () in

if curPalLen > maxPal.len {

maxPal = (palLens.count, curPalLen)

}

outer: while i < sLen {

// find the longest palindrome centered at current center position, i.e.

// palLens.count

if i > curPalLen && s[i] == s[i - curPalLen - 1] {

++i

curPalLen += 2

continue

}

updateMaxPal()

palLens.append(curPalLen)

// move to next center

// we can do this either naively by just moving to next center position

// of 2*n + 1 positions one by one:

// i = (palLens.count - 1) / 2 + 1

// palLen = palLens.count % 2

// or we could take advantage of the palindrome symmetry:

// a b a b a b a b a

// 0103050709070503010

// |

// |? ? ? ? ? ? ? ? ?

// 0??????????????????

// |

// a|? ? ? ? ? ? ? ?

// 01?????????????????

// |

// a|? ? ? ? ? ? ? ?

// 010????????????????

// |

// a b a|? ? ? ? ? ?

// 0103???????????????

// |

// a b a b a|? ? ? ?

// 010305?????????????

// |

// a b a b a b a|? ?

// 01030507???????????

// |

// a b a b a b a b a|

// 0103050709?????????

let curPalLeftHalfStartIdx = palLens.count - 1 - curPalLen

let curPalLeftHalfEndIdx = palLens.count - 2

for var j = curPalLeftHalfEndIdx; j >= curPalLeftHalfStartIdx; --j {

let distToLeftEdge = j - curPalLeftHalfStartIdx

if palLens[j] == distToLeftEdge {

curPalLen = distToLeftEdge

continue outer

}

palLens.append(min(distToLeftEdge, palLens[j]))

}

curPalLen = 1

++i

}

updateMaxPal()

let startIdx = maxPal.idx / 2 - maxPal.len / 2

return Array(s[startIdx..<startIdx + maxPal.len])

}

Check this out if you need to know more about this algorithm: http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Try It Yourself

1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:

$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution

The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)

Problem¹	Time²	Test Cases³	My Xcode Project⁴
Longest Palindromic Substring	2.413ms	Save (1997)	Save (1989)

Guan Gui

Prove Logs on Blockchain with Go and ProvenDB

FileHeader for Atom

A Beautiful Linear Time Python Regex Matcher via NFA

LeetCode in Swift: Longest Palindromic Substring

Problem Statement

My Solution in Swift

Try It Yourself

More Problems Solved in Swift

Prove Logs on Blockchain with Go and ProvenDB

FileHeader for Atom

A Beautiful Linear Time Python Regex Matcher via NFA

Problem Statement

My Solution in Swift

Try It Yourself

More Problems Solved in Swift

Share this:

Leave a Reply Cancel reply