leetcode: 5. Longest Palindromic Substring

problem

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

Brute Force - O(N^3) time

• timeout

DP - O(N^2) time

class Solution {
    fun longestPalindrome(s: String): String {   
        val len = s.length
        val dp = Array(len) { BooleanArray(len) { false }}
        // base cases
        for (i in 0 until len - 1) {
            dp[i][i] = true            
            dp[i][i + 1] = (s[i] == s[i + 1])
        }
        dp[len - 1][len - 1] = true
        // ex. babad
        // <base cases>
        //   0 1 2 3 4
        // 0 T F 
        // 1   T F
        // 2     T F
        // 3       T F
        // 4         T
        
        // i = 2, compare second 'b' and 'd'
        // i = 1, compare first 'a' and second 'a'. then, first 'a' and 'd'
        // i = 0, compare first 'b' and second 'b'. then, ...    
        // j is always greater than i.
        // The order of i is decreasing because dp[i][j] depends on dp[i + 1][j - 1] which means i depends on i + 1.
        for (i in (len - 3) downTo(0)) {
            for (j in i + 2 until len) {
                dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]
            }
        }
        // <result>
        //   0 1 2 3 4
        // 0 T F T F F
        // 1   T F T F
        // 2     T F F
        // 3       T F
        // 4         T
        
        var maxLen = 0
        var answer = ""
        for (i in 0 until len) {
            for (j in i until len) {
                if (dp[i][j] && maxLen < j - i+ 1) {
                    maxLen = j - i + 1
                    answer = s.substring(i, j + 1)
                }
            }
        }
        return answer
    }
}

Two Pointers - O(N^2) time

class Solution {
    fun longestPalindrome(s: String): String {   
        // minimum length of palindrom substring is 1
        var maxLen = 0
        var answer = ""
        for (i in s.indices) {
            // when the length of palindromic substring is odd
            val len1 = expandAroundCenter(s, i, i)
            // when the length of palindromic substring is even
            val len2 = expandAroundCenter(s, i, i + 1)
            // choose the longest length
            val candidate = maxOf(len1, len2)
            if (maxLen < candidate) {
                maxLen = candidate                
                val leftOffset = (candidate - 1) / 2
                val rightOffset = candidate / 2
                answer = s.substring(i - leftOffset, i + rightOffset+ 1)
            }
        }   
        return answer
    }
    
    fun expandAroundCenter(s: String, l: Int, r: Int): Int {
        var left = l
        var right = r
        val len = s.length
        while (left >= 0 && right < len && s[left] == s[right]) {
            left--
            right++
        }
        // unneeded addition & deletion is execueted in while loop
        left++
        right--
        // return length
        return right - left + 1
    }
}