Start learning free

LESSON 458 OF 540 · DYNAMIC PROGRAMMING

Longest Palindromic Substring in Kotlin: O(n²) Expand Around Center

Practice O(n2) Read the full explanation

You are given a string s. Return its longest palindromic substring. If several substrings have that greatest length, return the one that starts first, furthest to the left.

A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters of s: "bcd" is a substring of "abcde", but "ace" is not.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is a palindrome of length 3 too, but "bab" starts first.
No substring of length 4 or 5 is a palindrome.

Example 2:

Input: s = "cbbd"
Output: "bb"
Explanation: A palindrome of even length, like "bb", has its middle between two characters.

Example 3:

Input: s = "abacdfgdcaba"
Output: "aba"
Explanation: "aba" appears at the start and at the end, and the first one is returned.
"abacd" read backward is "dcaba", which also appears in s, but neither of them is a palindrome.

 

Constraints:

  • 1 <= s.length <= 1000
  • s is made of English letters and digits only. Uppercase and lowercase letters are different characters: "Aa" is not a palindrome.

Note:

Your algorithm should run in O(n2) time and use O(1) extra space besides the returned string, where n is the length of s.



Checking every substring on its own takes O(n3): about n2/2 substrings, each up to n characters long. Look at palindromes from the middle instead. Every palindrome has a center: its middle character when its length is odd, or the gap between its two middle characters when the length is even. A string of n characters has 2n - 1 centers: n characters and n - 1 gaps.

From a center, expand: start with two positions left and right (the same character, or two neighbours), and move them one step outward while both are inside s and their characters are equal. When they stop, the palindrome between them has right - left - 1 characters, and it is the longest one around that center. A helper that does this and returns the length, called for the centers (i, i) and (i, i + 1) of every i, finds the longest palindrome at each center.
A palindrome of length length centered at i starts at i - (length - 1) / 2, rounded down. Keep the best start and length, and replace them only by a strictly longer palindrome: the centers go from left to right, so the first of the longest ones stays.

There are 2n - 1 centers, and each expansion takes at most n / 2 steps: O(n2) time. Only a few numbers are kept: O(1) extra space, besides the returned string.
A table dp[i][j] telling whether s[i..j] is a palindrome works too, in the same time but with O(n2) space. Manacher's algorithm even finds the answer in O(n), but it goes beyond this lesson.
STEP 1 OF 14
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Longest Palindromic Substring in Kotlin, explained

    Problem overview

    The function longestPalindrome gets a string s and returns its longest palindromic substring. A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters, so "bcd" is a substring of "abcde" and "ace" is not. When several palindromes share the greatest length, the one that starts first wins.

    For "babad" the answer is "bab": "aba" has the same length, but "bab" starts further left. For "cbbd" it is "bb", an even-length palindrome. For "abacdfgdcaba" it is "aba", the first of its two occurrences. Uppercase and lowercase letters are different characters, so "Aa" is not a palindrome.

    Approach

    The brute force checks every substring: about n²/2 of them, each needing up to n comparisons, so O(n³). A palindrome gives a better handle. Every palindrome has a center: its middle character when the length is odd, or the gap between its two middle characters when the length is even. Starting from a center and moving outward, the palindrome grows for as long as the two characters at the ends match.

    So the plan is to visit every center and expand outward from it. A string of length n has n character centers and n - 1 gaps between characters. Each expansion takes at most about n / 2 steps, so the whole search is O(n²) time with only a few variables, which is O(1) extra space besides the returned string.

    A helper does the expanding. expand(s, left, right) takes the two starting ends, moves them outward while the characters match, and returns the length of the palindrome it found. From a real run on "babad":

    i=0 odd=1 even=0
i=1 odd=3 even=0
i=2 odd=3 even=0
i=3 odd=1 even=0
i=4 odd=1 even=0

    Here odd is expand(s, i, i) and even is expand(s, i, i + 1). The first length-3 palindrome appears at i = 1 ("bab"). At i = 2 the length is 3 again ("aba"), but it isn't larger than the best so far, so the first one stays. For "cbbd", only i = 1 gives something longer than 1: even=2, the gap between the two b's.

    Step by step

    1. Remember the best palindrome. Two variables, bestStart and bestLen, both 0, hold where the best palindrome starts and how long it is. Remembering these two numbers is enough; the substring is cut out once at the end.
    2. Visit every position. for (i in 0 until s.length). Each i gives two centers: the character s[i] and the gap right after it.
    3. Odd palindromes. expand(s, i, i) starts both ends on the same character, so it finds the longest palindrome with s[i] in the middle. Store it in odd.
    4. Even palindromes. expand(s, i, i + 1) starts the ends on neighbouring characters, so it finds the longest palindrome centered on the gap. If they differ, or i is the last index, the length is 0. Store it in even.
    5. Take the larger. val length = maxOf(odd, even) is the longest palindrome centered at i.
    6. Compare strictly. if (length > bestLen). A palindrome just as long as the best starts further right, and the one that starts first must win, so ties don't replace it.
    7. Compute the start. bestStart = i - (length - 1) / 2. An odd palindrome has (length - 1) / 2 characters before its middle s[i]. An even one has length / 2 - 1 characters before s[i], its left middle. With integer division both equal (length - 1) / 2. For length 3 that is 1, and for length 4 it is also 1.
    8. Save the length. bestLen = length.
    9. Cut out the answer. After the loop, s.substring(bestStart, bestStart + bestLen). The end index of substring is exclusive, so this takes exactly bestLen characters.
    10. Write expand. It is a method of the same class, so longestPalindrome calls it by name alone. It takes s: String, left: Int and right: Int and returns an Int.
    11. Copy the parameters. var left = left and var right = right.
    12. Loop while the ends match. The condition has three parts joined by &&: left >= 0, right < s.length and s[left] == s[right]. The first two keep both ends inside the string, and && stops at the first failure, so the characters are compared only when both indexes are valid.
    13. Move outward. left-- and right++.
    14. Return the length. The loop ends one step past the palindrome on both sides, so the palindrome runs from left + 1 to right - 1, which is right - left - 1 characters. If the starting characters differ, the loop never runs and the result is 0.

    The solution in Kotlin

    class Solution {
    fun longestPalindrome(s: String): String {
        var bestStart = 0
        var bestLen = 0
        for (i in 0 until s.length) {
            val odd = expand(s, i, i)
            val even = expand(s, i, i + 1)
            val length = maxOf(odd, even)
            if (length > bestLen) {
                bestStart = i - (length - 1) / 2
                bestLen = length
            }
        }
        return s.substring(bestStart, bestStart + bestLen)
    }
    fun expand(s: String, left: Int, right: Int): Int {
        var left = left
        var right = right
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            left--
            right++
        }
        return right - left - 1
    }
}

    Kotlin details worth knowing:

    • Parameters are read-only. Writing left-- on a parameter is a compile error: 'val' cannot be reassigned. That is why the function copies them into var variables first. A local variable with the same name hides the parameter for the rest of the function body, so left and right there refer to the copies.
    • s[left] reads a Char, and == on two Char values compares them by value.
    • / on two Int values drops the remainder. Here length - 1 is never negative, so dropping the remainder means rounding down.
    • substring(start, end) excludes end.

    Complexity

    There are 2n - 1 centers, and each expansion moves at most about n / 2 steps outward, so the time is O(n²); the worst case is a string like "aaaa", where every expansion goes far. The code keeps a handful of integer variables, so the extra space is O(1), apart from the returned substring.

    Edge cases and common mistakes

    • Only odd centers. Without the expand(s, i, i + 1) call, "cbbd" would give "b" instead of "bb".
    • Using >= in the comparison. A later palindrome of the same length would replace the earlier one. For "babad" the result would be "aba", not "bab".
    • Checking the characters before the bounds. s[left] == s[right] must come last in the condition; written first, it can read index -1 or s.length and throw an exception.
    • Returning right - left from expand. That is off by one: the ends have stepped past the palindrome by one position on each side.
    • Single character. "a" gives "a": the odd expansion returns 1, and the even one returns 0 because i + 1 is out of range.
    • No repeats. "ab" gives "a", the first single character, because ties keep the first.
    • Case matters. "Aa" gives "A".

    Testing

    Results from running the solution:

    • "babad": "bab"
    • "cbbd": "bb"
    • "abacdfgdcaba": "aba"
    • "a": "a"
    • "ab": "a"
    • "racecar": "racecar"
    • "aaaa": "aaaa"
    • "forgeeksskeegfor": "geeksskeeg"
    • "Aa": "A"
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free