Longest Palindromic Substring

In competitive programming and real-world applications, finding the longest palindromic substring is a common problem.
It’s not just about getting the correct answer but doing so within the time constraints.
This article will guide you through multiple approaches to solve the Longest Palindromic Substring problem, highlighting their respective trade-offs and providing insights into their application in iOS development.

You can find the original problem described on LeetCode.

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1
Input: s = "babad"
Output: "bab"
Explanation: “aba” is also a valid answer.

Example 2
Input: s = "cbbd"
Output: "bb"

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Problem Solving

First Approach: Naive Solution

The most straightforward approach involves checking all possible substrings of the input string and verifying if each one is a palindrome. The process is simple:

1. Generate all substrings of s.
2. Check each substring to see if it is a palindrome.
3. Track the longest palindrome found.

func longestPalindrome(_ s: String) -> String {
    var maxLength = 0
    var longestSubstr = ""

    let n = s.count
    let chars = Array(s)

    for i in 0..<n {
        for j in i..<n {
            let substr = String(chars[i...j])
            if isPalindrome(substr) && substr.count > maxLength {
                maxLength = substr.count
                longestSubstr = substr
            }
        }
    }

    return longestSubstr
}

func isPalindrome(_ s: String) -> Bool {
    return s == String(s.reversed())
}

Complexity Analysis

Time Complexity

The nested loops create all substrings O(n²), and checking if each is a palindrome takes O(n), leading to a cubic time complexity O(n³).

Space Complexity

We only use a constant amount of extra space, excluding the input and output. So the space complexity is O(1).

Expanding Around Center

A more efficient approach leverages the property that a palindrome mirrors around its center. By treating every character (and every pair of characters) as a potential center, we can expand outwards to find the longest palindrome centered there.

For each character in the string:

• Expand outwards while the characters on both sides are equal.
• Track the maximum length palindrome found during this process.

We consider both odd-length palindromes (centered at one character) and even-length palindromes (centered between two characters).

func longestPalindrome(_ s: String) -> String {
    guard !s.isEmpty else { return "" }

    let chars = Array(s)
    var start = 0
    var end = 0

    for i in 0..<chars.count {
        let len1 = expandAroundCenter(chars, i, i)
        let len2 = expandAroundCenter(chars, i, i + 1)
        let len = max(len1, len2)

        if len > end - start {
            start = i - (len - 1) / 2
            end = i + len / 2
        }
    }

    return String(chars[start...end])
}

func expandAroundCenter(_ chars: [Character], _ left: Int, _ right: Int) -> Int {
    var l = left
    var r = right
    while l >= 0 && r < chars.count && chars[l] == chars[r] {
        l -= 1
        r += 1
    }
    return r - l - 1
}

Complexity Analysis

Time Complexity

We expand around each center, which takes O(n) time for each of the n centers, resulting in O(n²) in total.

Space Complexity

The algorithm uses a constant amount of extra space, so O(1).

Dynamic Programming

Dynamic programming (DP) offers another way to solve this problem, particularly useful when we need to cache and reuse subproblem solutions. We create a DP table where dp[i][j] is true if the substring s[i...j] is a palindrome.

func longestPalindrome(_ s: String) -> String {
    let n = s.count
    if n < 2 { return s }

    var start = 0
    var maxLength = 1
    let chars = Array(s)

    var dp = Array(repeating: Array(repeating: false, count: n), count: n)

    for i in 0..<n {
        dp[i][i] = true
    }

    for length in 2...n {
        for i in 0...(n - length) {
            let j = i + length - 1
            if chars[i] == chars[j] && (length == 2 || dp[i + 1][j - 1]) {
                dp[i][j] = true
                if length > maxLength {
                    start = i
                    maxLength = length
                }
            }
        }
    }

    let end = start + maxLength
    return String(chars[start..<end])
}

Complexity Analysis

Time Complexity

The DP table requires O(n²) time to fill.

Space Complexity

The DP table requires O(n²) space.

Best Practices and Tips

Coding Practices

• Keep Functions Pure: Ensure that your palindrome-checking function does not modify the input. This makes it easier to reason about and test.
• Optimize Early: While premature optimization is generally discouraged, recognizing patterns that can be optimized—like expanding around centers—can be crucial in competitive programming and real-world scenarios.

Common Pitfalls

• Overlooking Edge Cases: Always consider edge cases such as empty strings or strings with all identical characters.
• Inefficient Implementations: Be wary of brute-force solutions in performance-sensitive contexts.

Testing

• Edge Cases: Test with empty strings, single characters, and strings where all characters are the same.
• Performance: Benchmark your solution with the maximum input size to ensure it meets time constraints.

Conclusion

We’ve explored the Longest Palindromic Substring problem from a naive approach to more sophisticated solutions like expanding around centers and dynamic programming. Each method has its own use cases, trade-offs, and complexities. In iOS development, efficiently solving such problems can lead to enhanced performance and user experience in your apps.

Further Reading

To deepen your understanding, explore topics like:

• Manacher’s Algorithm: An advanced algorithm that solves the problem in O(n) time.
• Dynamic Programming in iOS: Learn how to apply DP techniques to optimize various features in your apps.

Call to Action

Try implementing these solutions yourself, and think about how you might apply them to the app you’re currently building. Remember, understanding the trade-offs between different approaches is key to becoming a more effective developer.

By understanding the trade-offs between simplicity, time, and space efficiency, developers can choose the most appropriate algorithm based on the specific requirements of their application.