LESSON 227 OF 348 · TWO POINTERS

Palindrome Substrings in Kotlin: Checking Every Substring with Two Pointers

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 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

KOTLIN · TWO POINTERS

Palindrome Substrings in Kotlin, explained

Problem overview

The function countPalindromes takes a String named input and returns how many of its contiguous substrings are palindromes. A palindrome reads the same forwards and backwards. Substrings are counted by position: two substrings with the same letters but different start or end indices count separately.

For "abbcbc" the answer is 9. The six single letters are palindromes, and so are "bb", "bcb" and "cbc". The two b letters at different positions are counted separately, and so are the two c letters.

Approach: try every substring

A substring is fixed 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 tries all of them: two nested loops pick i and j, a helper checks whether input[i..j] is a palindrome, and a counter goes up for each success.

The helper compares characters from both ends of the range, moving inward, and stops at the first mismatch. It works on the original string using indices, so no substring objects are created.

The method is easy to write and check, though it does more work than needed, since it re-checks overlapping ranges from scratch. The second lesson on this problem counts palindromes by expanding outward from each centre instead.

On "abbcbc" (indices 0 to 5), the pairs (i, j) that pass are the six with i == j, plus (1, 2) for "bb", (2, 4) for "bcb" and (3, 5) for "cbc". Every other pair fails on its first comparison or a later one, for example (0, 1), where a differs from b. That gives 6 + 3 = 9.

The count n * (n + 1) / 2 comes from the loops themselves: for i = 0 the inner loop runs n times, for i = 1 it runs n - 1 times, and so on down to 1. For "abc" that is 3 + 2 + 1 = 6 substrings: a, ab, abc, b, bc and c. Knowing this number tells you how much work the outer part of the algorithm does, before the cost of the palindrome check is added.

Step by step

Declare result as a var set to 0. It counts palindromes found so far.
Loop i over 0 until input.length. This is the start of the substring.
Loop j over i until input.length. Starting at i allows one-letter substrings, and every range has its end at or after its start.
Test the range. If isPalindrome(input, i, j) is true, add 1 to result. The helper is written afterwards.
Return result once both loops finish.
Declare the helper isPalindrome above countPalindromes, taking input and two indices left and right, and returning a Boolean.
Copy the parameters into variables. Kotlin parameters are read-only, so l and r are var copies that can move.
Loop while l < r. The two pointers walk towards the middle.
Return false on a mismatch between input[l] and input[r].
Move the pointers: increment l and decrement r.
Return true after the loop, because every pair matched.

The solution in Kotlin

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

Kotlin details worth knowing:

Parameters are read-only. Writing left++ inside isPalindrome would not compile. That is why the function copies left and right into the var variables l and r.
until excludes the upper bound. 0 until input.length runs from 0 to the last index. For an empty string the range is empty and the function returns 0.
Indexing a string gives a Char. input[l] != input[r] compares two characters by value.
Nothing is copied. Passing a string and two indices is cheaper than calling substring for every range, which would allocate a new string each time.
Single letters pass automatically. When i == j, l < r is false at once, so the helper returns true. All n one-letter substrings are therefore counted.

Complexity

Time: O(n³). There are about n² / 2 substrings, and the check on each one takes up to half its length in comparisons, which is O(n). In practice, mismatches stop most checks early, but the worst case, a string such as "aaaa…", really does take cubic time.

Space: O(1). The code keeps a few integers and never builds substrings.

Edge cases and common mistakes

Empty string. Both loops are empty and the answer is 0.
One letter. "a" gives 1.
All the same letter. "aaa" gives 6, because all 6 substrings are palindromes: three of length 1, two of length 2 and one of length 3.
All different letters. "abc" gives 3: only the single letters count.
Counting distinct substrings. Position matters. In "abbcbc" the two b letters at indices 1 and 2 are two substrings, not one.
Starting j at i + 1. This skips every single-letter substring, so the count is too low by n.
Checking the whole range with a loop that never stops early. Returning false at the first mismatch is what keeps most checks short. Counting mismatches and testing at the end gives the same answer but does more work.

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