Problem overview
The function countPalindromes takes a string, input, and returns how many contiguous substrings of it are palindromes. Substrings at different positions count separately even when their letters are the same.
For "abbcbc" the answer is 9: the six single letters, plus "bb", "bcb" and "cbc".
Approach: every palindrome has a center
The simplest solution tests all substrings one by one, which costs about O(n³). This lesson uses a different observation: a palindrome is completely determined by its center and its length. If you know the middle, you can build the palindrome outward, one pair of characters at a time, and stop at the first pair that doesn't match.
There are two kinds of center:
- Odd length. One middle character, such as the
"c"in"bcb". The center is a single indexi, and the expansion starts withleft = iandright = i. - Even length. Two middle characters, such as
"bb". The center sits between indexiandi + 1, so the expansion starts withleft = iandright = i + 1.
From a center, each step checks that the two characters just outside the current substring are equal. If they are, the longer substring is a palindrome too, so it is counted. If not, no longer palindrome can have this center, because it would contain the mismatched pair. So the count for a center is the number of successful expansions.
On "abbcbc", the center at index 3 ("c") gives two palindromes: "c", then "bcb", and it stops when "b" meets "c". The center at index 4 ("b") also gives two: "b" and "cbc". The even center between indexes 1 and 2 gives one, "bb". Add up all centers and you reach 9.
Each palindrome is counted from exactly one center, so nothing is counted twice, and every palindrome has some center, so none is missed.
Step by step
- Start a counter.
result := 0will hold the total over all centers. - Loop over positions. Each index
iis a possible center. - Count odd palindromes. Call the helper
countPalindromesWithCenter(input, i, i)and add what it returns. Both pointers start on the same character, which is a palindrome of length 1. - Count even palindromes. Call it again with
iandi + 1. When the two characters differ, ori + 1is past the end, it simply returns 0. - Return the total after the loop.
- Declare the helper. It takes the string and the two starting indexes and returns an
int. - Keep a local counter. The helper has its own
result, separate from the caller's. - Loop while the expansion is valid. Three conditions joined by
&&:left >= 0,right < len(input)andinput[left] == input[right]. The order matters, as explained below. - Count the current substring. If the loop body runs,
input[left..right]is a palindrome. - Widen it. Decrement
leftand incrementrightso the next pass looks at the characters just outside. - Return the helper's counter.
The solution in Go
func countPalindromesWithCenter(input string, left int, right int) int {
result := 0
for left >= 0 && right < len(input) && input[left] == input[right] {
result++
left--
right++
}
return result
}
func countPalindromes(input string) int {
result := 0
for i := 0; i < len(input); i++ {
result += countPalindromesWithCenter(input, i, i)
result += countPalindromesWithCenter(input, i, i+1)
}
return result
}
The Go details worth knowing:
- Short-circuit
&&protects the indexing. Go evaluates the conditions from left to right and stops at the first false one. Whenleftis -1 orrightequalslen(input), the comparisoninput[left] == input[right]is never evaluated. If the bounds checks came last, the program would panic with an index out of range. - Parameters are copies. The helper modifies its own
leftandrightas it expands. The caller's variables stay as they were, soiis safe to reuse for the second call. forwith a condition is awhile. Go has no separatewhilekeyword. The helper's loop has no initializer and no post statement, because the body updates the indexes itself.- Bytes.
input[left]is a byte. That is fine for lowercase letters, where each character is one byte. Strings with multi-byte characters should be converted to[]runefirst. - Two functions, one file. The helper can be declared above or below
countPalindromes, because Go resolves package-level functions regardless of their order.
Complexity
Time: O(n²). There are 2n - 1 centers. Each expansion moves outward by at most about n / 2 steps, and it runs that long only in strings like "aaaa...a", where everything matches. So the total is bounded by n². For most strings the expansions stop after a step or two, and the loop is close to linear. That is a clear step down from the cubic cost of testing every substring from scratch.
Space: O(1). Only integers are kept, and the expansion is a loop, not recursion.
Edge cases and common mistakes
- Forgetting the even centers. Counting only from
(i, i)misses"bb", so"abbcbc"would give 8 instead of 9. - Index checks after the comparison. Putting
input[left] == input[right]first can read index -1 orlen(input), which panics at run time. - The last index. For
i = len(input) - 1, the even call hasright = len(input), which fails the bounds check immediately and returns 0. - Empty string. The loop doesn't run and the result is 0.
- Single letter.
"a"gives 1: the odd center counts it, and the even center adds nothing. - All the same letter.
"aaa"gives 6: the odd centers give 1, 2 and 1, and the two even centers give 1 each. - Counting by value. Palindromes are counted by position, so
"b"in"abbcbc"counts three times.
Testing
"abbcbc"gives 9."aaa"gives 6."abc"gives 3."a"gives 1.""gives 0.
The helper can also be tried on its own. On "abbcbc", countPalindromesWithCenter(input, 1, 2) returns 1, countPalindromesWithCenter(input, 3, 3) returns 2 and countPalindromesWithCenter(input, 2, 3) returns 0.
