Start learning free

LESSON 226 OF 347 · TWO POINTERS

Palindrome Substrings in C#: Brute Force Over All Substrings

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

    C# · TWO POINTERS

    Palindrome Substrings in C#, explained

    Problem overview

    CountPalindromes takes a string input and returns how many of its contiguous substrings are palindromes. Substrings are counted by position: two substrings with different start or end indexes are different, even when they have the same letters.

    For "abbcbc" the answer is 9. The palindromes are the six single characters a, b, b, c, b, c, plus bb, bcb and cbc. Every single character is a palindrome, so the answer for a non-empty string is at least its length.

    Approach

    A substring is determined by its first and last index, i and j with i <= j. The brute force tries every such pair and asks a helper, IsPalindrome(input, i, j), whether the characters from i to j read the same in both directions. Each true adds 1 to the count.

    The helper copies the substring, builds a reversed copy and compares the two. It is the simplest way to write the check, so the lesson uses it. It is not the cheapest, though. Each check takes time proportional to the substring's length, and there are about n²/2 substrings, so the whole algorithm is cubic. The next lesson on this problem counts palindromes by expanding outward from each center, which avoids the repeated work.

    Here is the idea for "abbcbc". With i = 1 the loop tries j from 1 to 5: "b" yes, "bb" yes, "bbc" no, "bbcb" no, "bbcbc" no. That start contributes 2 palindromes. Doing the same for every start gives 9 in total.

    The same helper could avoid the copies by comparing characters from both ends with two pointers, as a plain palindrome check does. That would save memory, but each check would still take linear time, so the total would stay cubic. The real improvement is to stop checking each substring separately, and that is what center expansion does: whenever a substring is not a palindrome, no larger substring around the same center can be one either, so the work stops early.

    Step by step

    1. Declare result as an int set to 0. Every palindromic substring adds exactly one.
    2. Loop over the start i from 0 up to but not including input.Length.
    3. Loop over the end j from i to the end. Starting at i rather than 0 visits each substring once, and includes the single characters, where j == i.
    4. Call the helper IsPalindrome(input, i, j) and increment result when it returns true. Writing the caller before the helper keeps each piece small.
    5. Return result after both loops.
    6. Declare the helper IsPalindrome above CountPalindromes, taking the string and two indices, both inclusive, and returning a bool.
    7. Implement it. Take first as input.Substring(left, right - left + 1), build second as the reverse of first, and return whether they are equal.

    The solution in C#

    class Solution {
    public bool IsPalindrome(string input, int left, int right) {
        string first = input.Substring(left, right - left + 1);
        string second = new string(first.Reverse().ToArray());
        return first == second;
    }

    public int CountPalindromes(string input) {
        int result = 0;
        for (int i = 0; i < input.Length; i++) {
            for (int j = i; j < input.Length; j++) {
                if (IsPalindrome(input, i, j)) {
                    result++;
                }
            }
        }
        return result;
    }
}

    The C# details are all in the helper:

    • Substring(start, length) takes a length, not an end index. That is why the code passes right - left + 1: the +1 makes the right end inclusive. Developers coming from Java, where the second argument is an end index, often get this wrong.
    • first.Reverse() is a LINQ method. A string has no instance method named Reverse. The call comes from System.Linq, which treats the string as a sequence of char and returns the characters in reverse order, without modifying the original.
    • ToArray() and new string(...). The reversed sequence is collected into a char[], and the string constructor turns that array back into a string.
    • == compares contents. For C# strings, first == second checks whether the two strings hold the same characters, so it is the right comparison. It doesn't ask whether they are the same object.

    Complexity

    Time: O(n³). The loops produce about n²/2 pairs. For each, IsPalindrome copies, reverses and compares a substring of up to n characters, which is O(n).

    Space: O(n). At any moment the helper holds a few strings and one array of at most n characters. The temporary strings are released after each call.

    Edge cases and common mistakes

    • The empty string. The outer loop never runs, so the result is 0.
    • Repeated letters. "aaa" has 6 palindromic substrings: three of length 1, two "aa" and one "aaa". Each position counts separately, so the two "aa" are different substrings.
    • Passing an end index to Substring. Writing input.Substring(left, right) reads the wrong number of characters and often throws ArgumentOutOfRangeException when left + right exceeds the length.
    • Starting j at 0. Then right < left for some pairs, and the length passed to Substring is zero or negative. Negative lengths throw.
    • Skipping single characters. They are palindromes, and the loops include them because j starts at i.

    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