LESSON 251 OF 414 · TWO POINTERS

Palindrome Substrings in Scala: O(n²) by Expanding Around Centers

Practice O(n²) 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 if they consist of same characters.

Example:

Input:  "abbcbc"

Output: 9

Explanation: ["a", "b", "b", "c", "b", "c", "bb", "bcb", "cbc"]

STEP 1 OF 10

Guided

Ctrl + Enter to check

SCALA · TWO POINTERS

Palindrome Substrings in Scala, explained

Problem overview

The method countPalindromes receives a string input and returns the number of its contiguous substrings that are palindromes. Substrings with different start or end positions are counted separately, even if their characters are the same.

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

Approach: grow each palindrome from its middle

The slower approach checks every substring from scratch, which takes O(n³) time. The faster way starts from the other end. Every palindrome has a center, and it grows outward from there: it stays a palindrome as long as the characters on its two sides match. So, instead of testing substrings, count the palindromes around each center.

There are two kinds of centers:

A palindrome of odd length has one middle character, so the center is a single index i, with left = i and right = i.
A palindrome of even length has two middle characters, so the center sits between i and i + 1, with left = i and right = i + 1.

For a center, expand outward: while left is still in the string, right is still in the string, and the two characters are equal, you have found one more palindrome, and then you move left one step left and right one step right. The first failed check ends the expansion, because a longer substring around the same center can't be a palindrome once an inner pair differs.

In "abbcbc" the odd centers at positions 0 to 5 contribute 1, 1, 1, 2, 2 and 1 palindromes. The count 2 at position 3 comes from c and bcb, and the count 2 at position 4 comes from b and cbc. Among the even centers, only the one between positions 1 and 2 matches (bb), and it contributes 1. The total is 8 + 1 = 9.

Step by step

Create result as a var starting at 0.
Loop over each index i in 0 until input.length. Each index is a possible center.
Count the odd palindromes. Call countPalindromesWithCenter(input, i, i) and add its result to result.
Count the even palindromes. Call countPalindromesWithCenter(input, i, i + 1) and add that. If the two middle characters differ, or i + 1 is past the end, the helper returns 0.
Return result as the last expression.
Write the helper above countPalindromes. It takes the string and the indices left and right, and returns an Int.
Make mutable copies l and r of the parameters, and a counter result starting at 0.
Write the loop condition: l >= 0 && r < input.length && input(l) == input(r). The index checks come first, because && stops at the first false operand, so the comparison is never evaluated with a bad index.
Inside the loop, add 1 to result and then expand: l -= 1 and r += 1.
Return result as the last expression of the helper.

The solution in Scala

class Solution {
    def 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 += 1
            l -= 1
            r += 1
        }
        result
    }

    def countPalindromes(input: String): Int = {
        var result = 0
        for (i <- 0 until input.length) {
            result += countPalindromesWithCenter(input, i, i)
            result += countPalindromesWithCenter(input, i, i + 1)
        }
        result
    }
}

The Scala details worth a closer look:

Short-circuit &&. When l is negative or r equals the length, the earlier condition is false and Scala doesn't evaluate input(l) == input(r). If the comparison came first, an exception would be thrown.
Parameters can't be reassigned, which is why l and r are copied into vars.
The last expression is the result. Neither method uses return. The final line result is the value each method gives back.
Two result variables. The one in the helper counts the palindromes for one center. The one in countPalindromes is the total. They are local to different methods, so they don't collide.
== on characters compares values, which is what the check needs.

Complexity

Time: O(n²). There are 2n - 1 centers. Expanding one center can take up to about n / 2 steps, so the total is at most about n² steps. For "aaaa", which is the worst case, every center expands as far as it can.

Space: O(1). The method uses a few integers and creates no substrings.

Edge cases and common mistakes

Empty string. The loop in countPalindromes runs zero times, so the result is 0.
One character. "a" gives 1. The even call has right = 1, which is not less than the length, so it returns 0.
All equal characters. "aaaa" gives 10, which matches the number of substrings.
Forgetting the even centers. "abba" would count only 4 single characters instead of 6, missing bb and abba.
Putting the comparison before the bounds checks. The helper would throw an exception on the first center at the edge of the string.
Counting only the longest palindrome per center. Every successful expansion step is a palindrome, so each adds 1. That is why the counter is inside the loop.

Testing

"abbcbc" gives 9.
"aaaa" gives 10.
"abc" gives 3.
"abba" gives 6.
"" gives 0.
For "abbcbc", the helper called as countPalindromesWithCenter(input, 1, 2) returns 1, and with (input, 0, 1) it returns 0.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free