LESSON 250 OF 414 · TWO POINTERS

Palindrome Substrings in Scala: Checking Every Substring in O(n³)

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 11

Guided

Ctrl + Enter to check

SCALA · TWO POINTERS

Palindrome Substrings in Scala, explained

Problem overview

The method countPalindromes receives a string input and returns how many of its contiguous substrings are palindromes. Substrings at different positions count separately, even when they contain the same characters.

For "abbcbc" the answer is 9. The palindromic substrings are the six single characters a, b, b, c, b, c, plus bb, bcb and cbc. The two b characters and the two c characters each count separately, because they sit at different positions.

Approach: try every substring

A substring is identified by its first index i and its last index j, with i <= j. A string of length n has n * (n + 1) / 2 of them. The direct approach tests each one with a palindrome check and counts the successes.

The palindrome check works on the original string, without cutting out the substring. It uses two pointers: l at the first index and r at the last one. While l < r, compare the characters. If they differ, the substring is not a palindrome. If they match, move both pointers inwards. If the pointers meet or cross without a mismatch, it is a palindrome. Every one-character substring passes at once, because l and r are equal and the loop never starts.

For "abbcbc" the loops visit 21 substrings, since 6 * 7 / 2 = 21, and 9 of them pass the check: the six single characters and bb, bcb and cbc. Every other pair of indices fails at its first or second comparison, such as ab (a against b) or abbc (a against c).

This approach is easy to get right, but it does a lot of repeated work: checking "abbcb" and then "bbcb" each starts from scratch. The next lesson on this problem counts around centers and does much less.

Step by step

Create result as a var starting at 0. It counts the palindromes.
Loop over the first index i with 0 until input.length.
Loop over the last index j with i until input.length. Starting at i includes the one-character substring.
Test the substring. If isPalindrome(input, i, j) is true, add 1 to result.
Return result after both loops.
Write isPalindrome above countPalindromes. It takes the string and the two indices left and right, and returns a Boolean.
Copy the indices into variables. Parameters can't be reassigned in Scala, so var l = left and var r = right give the loop something to change.
Loop while l < r, comparing characters from both ends.
On a mismatch, when input.charAt(l) != input.charAt(r), return false.
Move inwards with l += 1 and r -= 1.
Return true when the loop ends without a mismatch.

The solution in Scala

class Solution {
    def isPalindrome(input: String, left: Int, right: Int): Boolean = {
        var l = left
        var r = right
        while (l < r) {
            if (input.charAt(l) != input.charAt(r)) {
                return false
            }
            l += 1
            r -= 1
        }
        return true
    }
    def countPalindromes(input: String): Int = {
        var result = 0
        for (i <- 0 until input.length) {
            for (j <- i until input.length) {
                if (isPalindrome(input, i, j)) {
                    result += 1
                }
            }
        }
        return result
    }
}

The Scala details worth a closer look:

Parameters are values. left and right can't be changed, so the method copies them into the vars l and r.
input.charAt(l) is the Java String method, which Scala strings provide. input(l) reads the same character in the usual Scala style. Both work.
!= compares the two Char values by value.
Ranges. 0 until input.length stops before the length, while i until input.length starts at the current i. Each for over a range runs its body once per value.
Early return from a method. return false inside the while leaves isPalindrome immediately. The final return true is the normal ending.

A shorter version and its cost

The same idea can be written by cutting out each substring and comparing it with its reverse:

val input = "abbcbc"
var result = 0
for (i <- 0 until input.length; j <- i until input.length) {
  val sub = input.substring(i, j + 1)
  if (sub == sub.reverse) result += 1
}
println(result) // 9

Here one for holds both ranges, separated by a semicolon. The code is shorter, but substring and reverse each build a new string for every pair, so it uses extra memory and does not improve the O(n³) time. The version with two pointers avoids those copies.

Complexity

Time: O(n³). There are about n² / 2 pairs (i, j), and each check can compare up to half of the substring's characters, which is up to n / 2 comparisons. For a string of one repeated letter, such as "aaaa", every check goes all the way through.

Space: O(1). The method keeps a few integers and builds no substrings.

Edge cases and common mistakes

Empty string. Both loops run zero times, so the result is 0.
One character. "a" gives 1.
All characters equal. "aaaa" gives 10, which is 4 * 5 / 2: every substring is a palindrome.
No repeats. "abc" gives 3, one for each single character.
Even-length palindromes. "abba" gives 6: four single characters, bb and abba. The two-pointer check handles even and odd lengths the same way.
Starting j at i + 1. That drops all the one-character palindromes, and the example would give 3 instead of 9.
Counting distinct palindromes. The problem counts positions, not distinct texts. In "abbcbc" the letter b adds 3, not 1.
Running j up to input.length inclusive. The last valid index is input.length - 1, so until input.length is right. Using to would read one position past the end of the string and throw an exception.

Testing

"abbcbc" gives 9.
"aaaa" gives 10.
"abc" gives 3.
"abba" gives 6.
"" gives 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