LeetCode 5 in Swift: Longest Palindromic Substring

My first post of many showing my LeetCode journey :)

The problem

In this problem, we need to find the longest palindromic substring inside a given string.

A palindrome is a text that reads the same forward and backward, like "aba" or "abba".

My first approach

My first approach was to iterate through the received string and check each substring to see if it was a palindrome.

If it was, I checked if it was longer than the current longest palindrome found.

After that, I removed the first character from the received string and did everything again, covering the cases with different starting letters.

Here is the code:

class Solution {
    func longestPalindrome(_ s: String) -> String {
        var strInput = s
        var subStr = ""
        var longest = ""

        while strInput.count > longest.count {
            for char in strInput {
                subStr = subStr + String(char)

                if subStr == String(subStr.reversed()) {
                    if longest.count < subStr.count {
                        longest = subStr
                    }
                }
            }

            strInput = String(strInput.dropFirst())
            subStr = ""
        }

        return longest
    }
}

The code worked, but in one of LeetCode's test cases it timed out. It took too long to run.

This solution has a time complexity of O(n³).

The reason:

• The while loop runs up to n times.
• The for loop runs around n / 2 times on average for each while iteration.
• Checking if the substring is a palindrome is also O(n), because it reverses and compares the string.

So:

O(n) * O(n) * O(n) = O(n³)

That is too inefficient for large strings.

A better approach

After researching an explanation of the problem and a better way to approach it, I discovered the idea of expanding around the center of each palindrome.

The reason this works is that every palindrome has at least one center:

• One character in the center for odd-length palindromes, like "aba".
• Two equal characters in the center for even-length palindromes, like "abba".

Here is the version I developed. It is still not the best possible solution, but it passed all test cases:

class Solution {
    func longestPalindrome(_ s: String) -> String {
        guard s.count > 1 else { return s }

        let s = Array(s)

        // Function to expand from a center point
        func palindrome(_ center: Int) -> (start: Int, end: Int) {
            var l = center - 1
            var r = center + 1

            var res = (center, center)

            while l >= 0 && r < s.count {
                guard s[l] == s[r] else { break }

                res = (l, r)
                l -= 1
                r += 1
            }

            // For even-length palindromes
            var res1 = (center, center)

            if center < s.count - 1 && s[center] == s[center + 1] {
                l = center
                r = center + 1

                while l >= 0 && r < s.count {
                    guard s[l] == s[r] else { break }

                    res1 = (l, r)
                    l -= 1
                    r += 1
                }
            }

            // Return the longest palindrome found
            return res.1 - res.0 > res1.1 - res1.0 ? res : res1
        }

        var res = (0, 0)

        for i in 0..<s.count {
            let pal = palindrome(i)

            if pal.1 - pal.0 > res.1 - res.0 {
                res = pal
            }
        }

        return String(s[res.0...res.1])
    }
}

In this case, we do not create unnecessary substrings or reverse them, which results in a time complexity of O(n²).

The space complexity is O(n) because I convert the string into an array of characters to make indexing easier in Swift.

There is also a more advanced algorithm that solves this problem in O(n), called Manacher's Algorithm. But I will leave that one to study another time.

Thanks for following along until here! Feel free to leave comments or suggestions.

See you next time :)