5. Longest Palindromic Substring

Posted on | In |
  • Source : Link
  • Author : Han
  • Date : 2022-01-13

Problems

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

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    fun longestPalindrome(s: String): String {
        if (s.length < 2) return s

        var start: Int = 0
        var end: Int = 0
        var palSize: Int = 0

        fun expand(left: Int, right: Int) {
            var l: Int = left
            var r: Int = right

            while (l >= 0 && r < s.length && s[l] == s[r]) {
                l--
                r++
            }

            if (palSize < r - l - 1) {
                start = l + 1
                palSize = r - l - 1
                end = start + palSize
            }
        }
        s.indices.forEach {
            expand(it, it)
            expand(it, it + 1)
        }

        return s.substring(start, end)
    }
}

Time Out

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun longestPalindrome(s: String): String {
        var result = charArrayOf(s[0])
        s.forEachIndexed { i, char ->
            run {
                val arr: ArrayList<Char> = arrayListOf(char)
                s.removeRange(0, i + 1).forEachIndexed { _, c ->
                    run {
                        arr.add(c)
                        if (arr == arr.reversed() && arr.size > result.size) {
                            result = arr.toCharArray()
                        }
                    }
                }
            }
        }
        return result.joinToString("", "", "")
    }
}