Start learning free

LESSON 228 OF 348 · TWO POINTERS

Palindrome Substrings in Kotlin: Expanding Around Each Center in O(n²)

Practice O(n2) Read the full explanation

Given a string, count the number of palindromic contiguous substrings in the string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example:

Input:  "abbcbc"

Output: 9

Explanation: ["a", "b", "b", "c", "b", "c", "bb", "bcb", "cbc"]
STEP 1 OF 10
    Ctrl + Enter to check

    KOTLIN · TWO POINTERS

    Palindrome Substrings in Kotlin, explained

    Problem overview

    The function countPalindromes takes a String named input and returns the number of its contiguous substrings that are palindromes. Substrings with different start or end indices are different, even if they spell the same text.

    For "abbcbc" the answer is 9: the six single letters, plus "bb", "bcb" and "cbc".

    Approach: grow palindromes from their centers

    Checking every substring from scratch costs O(n³): about n² substrings, each checked in linear time. The faster idea uses a property of palindromes: a palindrome is a smaller palindrome with the same letter added on both sides. Start from a center, and if the letters on both sides match, you have found a palindrome. Widen by one on each side and test again. The first mismatch ends the search, because any wider range around the same center would contain that mismatched pair.

    Every palindrome has exactly one center:

    • an odd-length palindrome has a single middle letter, so the center is an index i and the expansion starts at (i, i);
    • an even-length palindrome has two middle letters, so the center sits between i and i + 1, and the expansion starts at (i, i + 1).

    Trying both kinds of center at every index finds each palindrome exactly once. A string of length n has 2n - 1 centers, and each expansion costs at most O(n), which gives O(n²) overall.

    On "abbcbc", the center at index 3 (c) finds "c" and then "bcb", and then stops, because the next pair, b and c, differs. It counts 2. The even center between indices 1 and 2 ("bb") finds "bb", and then stops at a versus c. The even center between indices 0 and 1 finds nothing, because a differs from b.

    Over the whole example, the calls for each i give these counts:

    iLetterOdd center (i, i)Even center (i, i + 1)
    0a10
    1b11
    2b10
    3c20
    4b20
    5c10

    The counts add up to 1 + 2 + 1 + 2 + 2 + 1 = 9. The odd center at index 4 finds "b" and "cbc", which uses the letters at indices 3 to 5.

    Step by step

    1. Declare result as a var set to 0 to hold the total.
    2. Loop i over 0 until input.length. Each index is a possible center.
    3. Add the odd centers. Call countPalindromesWithCenter(input, i, i) and add what it returns to result.
    4. Add the even centers. Call it again with (i, i + 1). If those two letters differ, or i + 1 is past the end, the helper returns 0.
    5. Return result after the loop.
    6. Declare the helper above countPalindromes. It takes the string and the starting indices left and right, and returns an Int: how many palindromes surround that center.
    7. Make mutable copies. Parameters can't be reassigned, so l and r are var copies, and a second var, result, starts at 0.
    8. Write the loop condition: l is at least 0, r is less than input.length, and input[l] == input[r]. Each pass through the loop means one more palindrome.
    9. Inside the loop, add 1 to result, then widen with l-- and r++.
    10. Return result after the loop.

    The solution in Kotlin

    class Solution {
    fun countPalindromesWithCenter(input: String, left: Int, right: Int): Int {
        var l = left
        var r = right
        var result = 0
        while (l >= 0 && r < input.length && input[l] == input[r]) {
            result++
            l--
            r++
        }
        return result
    }

    fun countPalindromes(input: String): Int {
        var result = 0
        for (i in 0 until input.length) {
            result += countPalindromesWithCenter(input, i, i)
            result += countPalindromesWithCenter(input, i, i + 1)
        }
        return result
    }
}

    Kotlin details worth knowing:

    • The order of the conditions matters. && stops at the first condition that is false. The index checks l >= 0 and r < input.length come before input[l] == input[r], so the string is never indexed outside its bounds, which would throw a StringIndexOutOfBoundsException.
    • == compares contents. On two Char values it tests whether they are the same character.
    • Two result variables. Each function has its own local result. They don't interfere, because a local variable exists only inside the function that declares it.
    • += with a function call. result += countPalindromesWithCenter(...) evaluates the call first and adds the returned count.
    • Parameters are read-only. That's why the helper copies left and right before moving them.

    The expansion loop is the usual two-pointer palindrome check run in reverse. Instead of starting at the ends and moving in, it starts at the middle and moves out, and it counts every step that succeeds. Because a successful step at width w implies success at every smaller width, no range is ever tested twice.

    Complexity

    Time: O(n²). There are 2n - 1 centers, and each expansion moves outwards at most about n / 2 steps. The worst case is a string like "aaaa…", where almost every expansion reaches the edge. For a typical string with few repeats, most expansions end after one or two steps.

    Space: O(1). Only a few integers are used.

    Edge cases and common mistakes

    • Empty string. The loop doesn't run and the result is 0.
    • One letter. "a" gives 1. The odd center counts it, and the even center at (0, 1) fails the r < input.length test.
    • All the same letter. "aaa" gives 6, the largest possible count for length 3.
    • All different letters. "abc" gives 3: just the single letters.
    • Forgetting the even centers. Without the (i, i + 1) call, "bb" is missed.
    • Reordering the loop condition. Putting input[l] == input[r] first makes the code throw at the edges, for example with l = -1.

    Testing

    • "abbcbc" gives 9.
    • "aaa" gives 6.
    • "abc" gives 3.
    • "a" gives 1.
    • "" gives 0.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free