Palindrome Substrings in C++ (Time Complexity: O(n^2))

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"]

Understanding the Problem

The core challenge of this problem is to identify all substrings of a given string that are palindromic. A palindrome is a string that reads the same forward and backward. The significance of this problem lies in its applications in text processing, DNA sequence analysis, and other fields where pattern recognition is crucial.

Potential pitfalls include not accounting for overlapping substrings and not efficiently checking for palindromes, which can lead to suboptimal solutions.

Approach

To solve this problem, we can use a dynamic programming approach to efficiently count palindromic substrings. Here's a step-by-step breakdown:

Naive Solution

A naive solution would involve generating all possible substrings and checking each one for being a palindrome. This approach is not optimal due to its high time complexity of O(n^3).

Optimized Solution

We can optimize the solution using dynamic programming. The idea is to use a 2D table to store whether a substring is a palindrome. We can build this table in O(n^2) time.

Steps:

Initialize a 2D array dp where dp[i][j] will be true if the substring from index i to j is a palindrome.
All substrings of length 1 are palindromes.
Check substrings of length 2 and mark them as palindromes if both characters are the same.
For substrings longer than 2, use the previously computed results to determine if the current substring is a palindrome.

Algorithm

Here is the step-by-step breakdown of the dynamic programming approach:

Create a 2D array dp of size n x n initialized to false.
For each character in the string, mark dp[i][i] as true (single character substrings).
For each pair of consecutive characters, mark dp[i][i+1] as true if they are the same.
For substrings longer than 2, use the relation dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1].
Count all true values in the dp array to get the number of palindromic substrings.

Code Implementation


#include <iostream>
#include <vector>
#include <string>

using namespace std;

int countPalindromicSubstrings(const string& s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int count = 0;

    // Single character substrings
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        count++;
    }

    // Two character substrings
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }

    // Substrings longer than 2 characters
    for (int length = 3; length <= n; ++length) {
        for (int i = 0; i < n - length + 1; ++i) {
            int j = i + length - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }

    return count;
}

int main() {
    string s = "abbcbc";
    cout << "Number of palindromic substrings: " << countPalindromicSubstrings(s) << endl;
    return 0;
}

Complexity Analysis

The time complexity of the dynamic programming approach is O(n^2) because we are filling an n x n table. The space complexity is also O(n^2) due to the storage of the table.

Edge Cases

Consider edge cases such as an empty string, a string with all identical characters, and a string with no palindromic substrings. The algorithm handles these cases effectively by initializing the table and checking conditions appropriately.

Testing

To test the solution comprehensively, consider the following test cases:

Empty string: ""
Single character string: "a"
String with all identical characters: "aaaa"
String with no palindromic substrings: "abc"
String with mixed characters: "abbcbc"

Thinking and Problem-Solving Tips

When approaching such problems, break down the problem into smaller parts and think about how to use previously computed results to build the solution. Practice dynamic programming problems to improve your problem-solving skills.

Conclusion

Understanding and solving problems related to palindromic substrings is crucial for various applications. By using dynamic programming, we can efficiently count palindromic substrings in a given string. Practice and explore further to enhance your skills.