Start learning free

LESSON 227 OF 347 · TWO POINTERS

Palindrome Substrings in C#: O(n²) by Expanding Around Centers

Practice O(n2) 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 10
    Ctrl + Enter to check

    C# · TWO POINTERS

    Palindrome Substrings in C#, explained

    Problem overview

    CountPalindromes takes a string input and returns the number of palindromic contiguous substrings. Substrings with different start or end indexes are counted separately, even when the letters are the same. For "abbcbc" the answer is 9: the six single letters, bb, bcb and cbc.

    Approach

    The first approach to this problem tests every substring, copying and reversing each one, which costs O(n³). This lesson uses a different view. Every palindrome has a center, and it can be grown outward from there:

    • An odd-length palindrome has one middle character. Its center is a single index i.
    • An even-length palindrome has two middle characters, which must be equal. Its center sits between indexes i and i + 1.

    Starting from a center, the helper compares the characters on the two sides. If they match, that is one more palindrome, and the window grows by one on each side. If they differ, or the window runs off either end of the string, no wider window around this center can be a palindrome, so the helper stops. The number of matches it found is the number of palindromes with that center.

    A string of length n has n odd centers and n - 1 even centers. Every palindromic substring has exactly one center, so adding up the counts from all of them gives each palindrome once.

    For "abbcbc" the odd centers give 1, 1, 1, 2, 2, 1. The two 2s come from the c at index 3, which also yields bcb, and the b at index 4, which also yields cbc. That sums to 8. The even centers give one match, bb, between indexes 1 and 2, for a total of 9.

    One expansion in detail

    Take the odd center at index 3 of "abbcbc". The helper starts with left = 3 and right = 3. Both point at c, so the count becomes 1 and the window widens to indexes 2 and 4. Both hold b, so the count becomes 2 and the window widens to 1 and 5. Now input[1] is b and input[5] is c, so the loop ends and the helper returns 2: the palindromes c and bcb. The work stopped at the first mismatch and never looked at a.

    Step by step

    1. Declare result in CountPalindromes, starting at 0.
    2. Loop over every index i as a possible center.
    3. Add the odd-length count by calling CountPalindromesWithCenter(input, i, i). Both pointers start on the same character.
    4. Add the even-length count with CountPalindromesWithCenter(input, i, i + 1). If those two characters differ, the helper returns 0 immediately.
    5. Return result after the loop.
    6. Write the helper. It takes the string and two indices left and right, and returns an int.
    7. Start its own result at 0 and loop while left is at least 0, right is less than input.Length, and input[left] equals input[right].
    8. Inside the loop, count the palindrome, then widen the window: left goes down by one and right goes up by one.
    9. Return the count when the loop ends.

    The solution in C#

    class Solution {
    public int CountPalindromesWithCenter(string input, int left, int right) {
        int result = 0;
        while (0 <= left && right < input.Length &&
            input[left] == input[right]) {
            result += 1;
            left -= 1;
            right += 1;
        }
        return result;
    }
    public int CountPalindromes(string input) {
        int result = 0;
        for (int i = 0; i < input.Length; i++) {
            result += CountPalindromesWithCenter(input, i, i);
            result += CountPalindromesWithCenter(input, i, i + 1);
        }
        return result;
    }
}

    C# details:

    • Short-circuit &&. C# evaluates the conditions left to right and stops at the first false one. The two index checks come before input[left] == input[right], so the string is never indexed with -1 or with input.Length. Reordering the checks would throw IndexOutOfRangeException.
    • Parameters are copies. The helper changes left and right freely. They are separate local variables, and the caller's i is unaffected.
    • Comparing char values. input[left] == input[right] compares two characters directly, with no string created.
    • The call at the last index is safe. For the last i, the even-center call starts with right equal to the length, so it fails the right < input.Length test first and returns 0.

    Complexity

    Time: O(n²). There are 2n - 1 centers, and expanding from one takes at most about n/2 steps. The worst case is a string of one repeated letter such as "aaaa", where every window keeps matching. A string with few matches finishes much faster, since expansion stops at the first mismatch.

    Space: O(1). Only integers are stored. No substrings are created.

    Edge cases and common mistakes

    • Forgetting the even centers. Without the second call, bb in the example is missed, and the result is 8.
    • Counting a palindrome twice. Each palindrome has one center, so odd and even centers never overlap. The count is exact.
    • Checking the characters before the bounds. Putting input[left] == input[right] first in the condition crashes at the string's edges.
    • The empty string. The loop doesn't run, so the result is 0.
    • All the same letter. "aaa" gives 6, since the three single letters, two "aa" and one "aaa" are counted. This is also the slowest input for the algorithm.

    Testing

    • "abbcbc" gives 9.
    • "aaa" gives 6.
    • "" gives 0.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free