Problem overview
The method countPalindromes receives a string, input, and returns the number of its contiguous substrings that are palindromes. Substrings at different positions count separately, even when they spell the same text.
For "abbcbc" the answer is 9: the six single letters, "bb", "bcb" and "cbc".
Approach: grow each palindrome from its center
The brute-force way checks every substring from scratch, about n²/2 substrings with up to n / 2 comparisons each, which is O(n³). Much of that work repeats: if "bcb" is a palindrome, checking "abcba" needs only the outer pair, not the inside again.
Every palindrome has a center, and it is fully determined by that center and its length. A palindrome of odd length has a middle character. A palindrome of even length has a gap in the middle, between two equal characters. There are 2n - 1 centers in a string of length n: n characters and n - 1 gaps.
For each center, start with the smallest candidate and expand outward one step at a time. Move l one step left and r one step right. While input[l] == input[r], the substring between them is a palindrome and the count grows. The first time the two characters differ, or an index leaves the string, no larger palindrome around this center exists, so stop.
In "abbcbc", the center on the second b (index 2) gives "b", then compares input[1] and input[3], which are b and c. They differ, so that center contributes 1. The gap between indices 1 and 2 starts with b and b, which match, so "bb" counts. The next pair, a and c, differs, so that center contributes 1.
Step by step
- Convert the string to an array of characters. Swift strings can't be indexed with integers, so
let chars = Array(input)gives a[Character].resultis avarstarting at 0. - Loop
iover0..<chars.count. Each index is a possible center. - Count the odd-length palindromes centered on
i. The helpercountPalindromesWithCenter(chars, i, i)starts with both pointers on the same character. Add what it returns toresult. - Count the even-length palindromes centered between
iandi + 1withcountPalindromesWithCenter(chars, i, i + 1). If those two characters differ, the helper returns 0. For the last index,i + 1is past the end, and the helper's bounds check returns 0 as well. - Return
resultafter the loop. - Declare the helper above
countPalindromes. It takes a[Character]and twoIntindices, all three with_so calls need no argument labels, and returns anInt. - Make copies. Parameters are constants, so
var l = leftandvar r = rightare the pointers that move. Avar result = 0counts the palindromes for this center. - Write the loop condition.
while l >= 0 && r < input.count && input[l] == input[r]. The index checks come first:&&stops at the first false condition, soinput[l]is read only when both indices are valid. - Count and expand. In the body, add 1 to
result, then decrementland incrementr. - Return
resultafter the loop.
The solution in Swift
class Solution {
func countPalindromesWithCenter(_ input: [Character], _ left: Int, _ right: Int) -> Int {
var l = left
var r = right
var result = 0
while l >= 0 && r < input.count && input[l] == input[r] {
result += 1
l -= 1
r += 1
}
return result
}
func countPalindromes(_ input: String) -> Int {
let chars = Array(input)
var result = 0
for i in 0..<chars.count {
result += countPalindromesWithCenter(chars, i, i)
result += countPalindromesWithCenter(chars, i, i + 1)
}
return result
}
}
Swift details worth knowing:
- Short-circuit evaluation. The order of the three conditions matters. If
input[l] == input[r]came first, an out-of-range index would crash the program, since Swift checks array bounds at run time. - Negative indices.
lcan drop to -1 before the loop stops. That is fine for anInt, and the conditionl >= 0catches it before the array is read. AUIntcould not go below 0 and would trap instead. Charactercomparison.Array(input)splits the string intoCharactervalues, which stand for what a reader sees as one character. They compare with==directly, so text outside ASCII is counted correctly:"é"gives 1 and"日本"gives 2.- Unlabeled parameters. Without
_, the call would have to be writtencountPalindromesWithCenter(input: chars, left: i, right: i). - Two variables named
result. The helper has its own localresult, separate from the one incountPalindromes.
Complexity
Time: O(n²). There are 2n - 1 centers. Each expansion can run up to about n / 2 steps, and a string of one repeated letter reaches that bound. Each step does constant work. The brute-force version costs O(n³).
Space: O(n). The character array holds n elements. The expansion itself uses a few integers.
Edge cases and common mistakes
- Empty string. The loop doesn't run and the method returns 0.
- One character.
"a"returns 1. The even center calls the helper withr = 1, which is out of range, and gets 0. - Repeated letters.
"aaa"returns 6 and"aaaa"returns 10. Every substring is a palindrome, and the expansions run as far as the borders allow. - No repeated neighbours.
"abc"returns 3: each odd center gives 1, and each even center gives 0. - Forgetting the even centers. Calling the helper only with
(i, i)misses"bb", so"abbcbc"would give 8. - Counting once per center instead of once per palindrome. The helper counts every step of the expansion, since each step yields a new palindrome. Counting only the final length gives too small an answer for a string like
"aaa". - Wrong order of conditions. Reading
input[l]before checkingl >= 0crashes as soon as an expansion reaches the start of the string.
Testing
"abbcbc"gives9.""gives0."a"gives1."abc"gives3."aaa"gives6."aaaa"gives10.
