Palindrome Substrings II in JavaScript (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 contiguous substrings of a given string that are palindromes. 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 missing substrings that are palindromes or counting the same substring multiple times. It's important to ensure that each unique start and end index combination is considered.

Approach

To solve this problem, we can use a dynamic programming approach. The naive solution would involve checking all possible substrings, which would be inefficient. Instead, we can use a 2D array to keep track of palindromic substrings and build our solution iteratively.

Naive Solution

The naive solution involves generating all possible substrings and checking each one for being a palindrome. This approach has a time complexity of O(n^3) and is not optimal for large strings.

Optimized Solution

We can optimize the solution using dynamic programming. The idea is to use a 2D array where dp[i][j] is true if the substring from index i to j is a palindrome. We can build this table iteratively:

All single characters are palindromes.
Check for palindromes of length 2.
Use previously computed results to check for longer palindromes.

Algorithm

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

Initialize a 2D array dp where dp[i][j] is true if the substring from index i to j is a palindrome.
All single characters are palindromes, so set dp[i][i] to true for all i.
Check for palindromes of length 2 and set dp[i][i+1] to true if s[i] == s[i+1].
For substrings longer than 2, set dp[i][j] to true if s[i] == s[j] and dp[i+1][j-1] is true.
Count all true values in the dp array to get the number of palindromic substrings.

Code Implementation


// Function to count palindromic substrings
function countPalindromicSubstrings(s) {
    const n = s.length;
    let count = 0;

    // Create a 2D array to store the palindrome status
    const dp = Array.from({ length: n }, () => Array(n).fill(false));

    // Single characters are palindromes
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }

    // Check for palindromes of length 2
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }

    // Check for palindromes of length greater than 2
    for (let length = 3; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }

    return count;
}

// Example usage
const input = "abbcbc";
console.log(countPalindromicSubstrings(input)); // Output: 9

Complexity Analysis

The time complexity of this 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 dp array. This is a significant improvement over the naive O(n^3) approach.

Edge Cases

Potential edge cases include:

Empty string: The output should be 0.
String with all identical characters: Every substring is a palindrome.
String with no palindromic substrings longer than 1 character.

Testing these edge cases ensures the robustness of the solution.

Testing

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

Input: "", Output: 0
Input: "a", Output: 1
Input: "aaa", Output: 6
Input: "abc", Output: 3

Using a testing framework like Jest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, it's important to:

Break down the problem into smaller subproblems.
Consider both naive and optimized solutions.
Use dynamic programming to store intermediate results and avoid redundant calculations.

Practicing similar problems and studying algorithms can significantly improve problem-solving skills.

Conclusion

In this blog post, we discussed how to count palindromic substrings in a given string using a dynamic programming approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice, consider the following resources: