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 their characters are the same.
For "abbcbc" the answer is 9: the six single characters, plus "bb", "bcb" and "cbc".
Approach: every palindrome has a center
Testing every substring from scratch costs O(n³), because each test can walk across the whole substring. That repeats a lot of work: if "bcb" is a palindrome, then "abcba" is one exactly when the characters just outside it, a and a, match.
This idea is the key. A palindrome is determined by its center and its size, and it grows by one character on each side as long as the new outer characters are equal. So instead of testing substrings, pick a center and expand outward while the two sides match. Every step that succeeds is one more palindrome around that center, and the first failure stops the expansion: no larger substring around the same center can be a palindrome, because it would contain the failing pair.
There are two kinds of centers:
- A palindrome of odd length has one middle character, at index
i. Expansion starts withleft = iandright = i. - A palindrome of even length has two middle characters, at
iandi + 1. Expansion starts withleft = iandright = i + 1. If those two characters differ, no palindrome has this center, and the count is 0.
Take "abbcbc" with the odd center at index 3, the c. The single "c" counts. The neighbours at indices 2 and 4 are b and b, so "bcb" counts too. Next come indices 1 and 5, b and c, which differ, so the expansion stops. This center contributes 2. The odd center at index 2, the b, contributes only 1, since its neighbours b and c differ at once.
Step by step
- Declare
resultas 0 withlet. Each palindrome will be added to it once, from its center. - Loop
ifrom 0 up to, but not including,input.length. Each index is a possible center. - Add the odd-length palindromes. Call
this.countPalindromesWithCenter(input, i, i)and add the returned value toresult. The lesson assumes the helper exists and writes it afterwards. - Add the even-length palindromes. Call the helper with
iandi + 1. At the last index,i + 1is outside the string, and the helper's bounds check makes it return 0. - Return
resultafter the loop. - Declare the helper,
countPalindromesWithCenter, taking the string and twonumberindices,leftandright, and returning anumber. - Declare its own
resultas 0. - Loop while the pair is valid:
leftis at least 0,rightis belowinput.length, and the characters at the two indices are equal. The bounds checks come first, and&&stops at the first false condition, so the comparison never reads outside the string. - Count and expand. Inside the loop, add 1 to
resultbecause the current substring is a palindrome. Then decreaseleftand increaserightto look at the next pair outward. - Return
resultafter the loop.
The solution in TypeScript
class Solution {
countPalindromesWithCenter(input: string, left: number, right: number): number {
let result = 0;
while (0 <= left && right < input.length &&
input[left] == input[right]) {
result += 1;
left -= 1;
right += 1;
}
return result;
}
countPalindromes(input: string): number {
let result = 0;
for (let i = 0; i < input.length; i++) {
result += this.countPalindromesWithCenter(input, i, i);
result += this.countPalindromesWithCenter(input, i, i + 1);
}
return result;
}
}
The TypeScript details worth knowing:
- Order of the conditions.
input[left]withleft = -1givesundefined, not an error, because out-of-range reads on a string don't throw. The checks onleftandrightcome first so the loop stops before such a read matters. ==between two strings. When both sides are strings,==and===give the same result: they compare the characters. The strict form===is the usual habit, because==converts types when they differ.- The same name twice. Both methods have a local
result. They are separate variables, each local to its own method. - Methods called through
this. The helper is reached asthis.countPalindromesWithCenter(...).
Complexity
Time: O(n²). There are 2n - 1 centers. Expanding from one center takes at most about n / 2 steps, since it stops at the edge of the string. A string of identical characters is the worst case, where every expansion runs until it reaches an edge. The total is at most proportional to n², and for most strings it is much less, because expansions stop at the first mismatch.
Space: O(1). The code keeps a few numbers and creates no substrings.
Edge cases and common mistakes
- Empty string. The loop doesn't run and the result is 0.
- Identical characters.
"aaa"gives 6, the maximum for length 3: three single characters, two of length 2 and one of length 3. - No repeated neighbours.
"abc"gives 3. All even centers return 0 immediately. - Forgetting the even centers. Only expanding from
(i, i)misses palindromes such as"bb". For"abbcbc"it would give 8 instead of 9. - Counting a center twice. Each palindrome has one center, so adding the odd and even counts together never counts a substring twice.
Testing
"abbcbc"gives9."abc"gives3."aaa"gives6.""gives0.