Problem overview
The function countPalindromes receives a string, input, and returns how many of its contiguous substrings are palindromes, meaning they read the same forwards and backwards. Substrings are counted by position: if the same letters appear at two different places, they count twice. Every single character is a palindrome of length 1.
For "abbcbc" the answer is 9. The six single letters give 6. Then "bb" (positions 1 to 2), "bcb" (positions 2 to 4) and "cbc" (positions 3 to 5) add 3 more. No other substring reads the same in both directions.
Approach: try every substring and test it
A substring is fixed by two positions: where it starts, i, and where it ends, j, with j >= i. A string of length n has n * (n + 1) / 2 such pairs, so a double loop can visit all of them exactly once. For each pair, a separate helper answers one question: is input[i..j] a palindrome? Whenever it is, the counter goes up.
The helper uses two pointers. One starts at the left end and one at the right end, and they walk toward each other. If the characters under them ever differ, the substring is not a palindrome. If the pointers meet or cross without a mismatch, every mirrored pair matched, so it is one. A substring of length 1 has left == right from the start, so the loop never runs and the answer is true, which is right.
This is the straightforward approach, and it is easy to get right. Its cost is the part to remember: there are about n²/2 substrings and each check can take up to n / 2 steps, so the total grows like n³. The next lesson on this problem counts the same palindromes by growing them outward from their centers, which is much faster.
Step by step
- Start a counter.
result := 0holds the number of palindromic substrings found so far. - Loop over start positions.
iruns from 0 tolen(input) - 1and marks where a substring begins. - Loop over end positions. For each
i,jruns fromito the last index. Starting ati(noti + 1) is what includes the one-character substrings. - Ask the helper. The
ifcallsisPalindrome(input, i, j)and incrementsresultwhen it returnstrue. Writing the call first, before the helper exists, lets you focus on the counting logic. - Return the counter after both loops finish.
- Declare the helper.
isPalindrometakes the string and twointpositions and returns abool. - Loop while
left < right. Go has nowhile, so aforwith only a condition does the job. When the pointers meet or cross, nothing is left to compare. - Return
falseon a mismatch. One differing pair is enough to rule the substring out, so there is no reason to keep comparing. - Move the pointers inward.
left++andright--bring the next pair into view. - Return
trueafter the loop. If every pair matched, the substring is a palindrome.
The solution in Go
func isPalindrome(input string, left int, right int) bool {
for left < right {
if input[left] != input[right] {
return false
}
left++
right--
}
return true
}
func countPalindromes(input string) int {
result := 0
for i := 0; i < len(input); i++ {
for j := i; j < len(input); j++ {
if isPalindrome(input, i, j) {
result++
}
}
}
return result
}
The Go details worth knowing:
- Bytes, not characters.
input[left]is abyte, the raw byte at that position. For plain lowercase letters, one byte is one character, so comparing bytes is correct. A string with multi-byte characters would need to be converted to a[]runefirst, because indexing would otherwise land inside a character. - Parameters are copies.
leftandrightare ordinaryintvalues passed by value. The helper changes its own copies freely and the caller'siandjare untouched:
l, r := 1, 3
isPalindrome("abbcbc", l, r)
fmt.Println(l, r) // 1 3
foris the only loop.for left < right { ... }is Go'swhile, and the three-part formfor i := 0; i < len(input); i++is the counting loop.:=declares and infers.result := 0creates anint. Go refuses to compile a variable that is declared and never used, so every name here is read somewhere.- Strings are immutable. The helper never copies or builds substrings. It reads characters of
inputin place by index, which keeps each check free of allocation.
Complexity
Time: O(n³). The two loops visit n * (n + 1) / 2 substrings. Each call to isPalindrome does at most half the substring's length in comparisons, which is up to about n / 2. Multiplying the two gives a cubic bound. A mismatch ends most checks early on typical text, but a string such as "aaaa...a" makes every check run to the end.
Space: O(1). The solution keeps a few integers. It never builds a substring.
Edge cases and common mistakes
- Empty string. The outer loop never runs and the function returns 0.
- Single character.
"a"returns 1, because the only substring is a palindrome of length 1. - All the same letter.
"aaa"returns 6: three substrings of length 1, two of length 2 and one of length 3. Equal substrings at different positions are counted separately, as the problem requires. - No repeated neighbors.
"abc"returns 3, only the single letters. - Starting
jati + 1. That skips every single-letter substring, so the count comes out too small bylen(input). - Using
left <= rightin the helper. This still gives the right answer, since comparing a character with itself always matches, but it does one pointless comparison on odd lengths. - Counting distinct strings. Putting substrings in a set would count
"b"once instead of three times in"abbcbc"and give the wrong answer.
Testing
"abbcbc"gives 9."aaa"gives 6."abc"gives 3."a"gives 1.""gives 0.
