LeetCode: 5. Longest Palindromic Substring

LeetCode: 5. Longest Palindromic Substring

Problem: 5. Longest Palindromic Substring

Link: https://leetcode.com/problems/longest-palindromic-substring/

Algorithm: https://www.youtube.com/watch?v=nbTSfrEfo6M

Difficulty: Medium

Description:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

Solution:

Language: Swift

Runtime: 36ms
Memory: 4.0MB

Copy to Clipboard

class Solution {
    func longestPalindrome(_ s: String) -> String {
        if s.count < 2 {
            return s
        }
        
        var charaterArray: [Character] = ["#"]
        for c in s {
            charaterArray.append(c)
            charaterArray.append("#")
        }
        
        var p : [Int] = Array(repeating: 0, count: charaterArray.count)
        
        var center = 0
        var right = 0
        var mirror = 0
        
        var resultCenter = 0
        var resultRight = 0
        
        for i in 0 ..< charaterArray.count {
            mirror = 2 * center - i
            
            if i < right {
                p[i] = min(p[mirror], right - i)
            }
            
            while (i - p[i] >= 0 && i + p[i] < charaterArray.count && charaterArray[i + p[i]] == charaterArray[i - p[i]]) {
                p[i] += 1
            }
            
            if i + p[i] > right {
                center = i
                right = i + p[i]
            }
            
            if p[i] > resultRight {
                resultCenter = i
                resultRight = p[i]
            }
        }
        
        let firstIndex = s.index(s.startIndex, offsetBy: (resultCenter - (resultRight - 1)) / 2)
        let lastIndex = s.index(s.startIndex, offsetBy: (resultCenter + (resultRight - 1)) / 2)
        
        return String(s[firstIndex ..< lastIndex])
    }
}

Related Posts

Leave A Comment Cancel reply