Counting Palindromic Substrings

This section addresses the problem of counting all palindromic substrings within a given string, similar to LeetCode problem 647.

Problem Description

Given a string s, determine and return the total count of palindromic substrings. A substring is a contiguous sequence of charcaters. A palindromic string reads the same forwards and backwards. Substrings with different start or end positions are considered distinct, even if composed of the same characters.

Dynamic Programming Approach

We can efficiently solve this using dynamic programming by pre-calculating whether every possible substring is a palindrome. This information is stored in a 2D boolean array.

1. State Definition

Let isPalindrome[i][j] be a boolean value indicating whether the substring of s starting at index i and ending at index j (inclusive, i.e., s[i...j]) is a palindrome. We are primarily interested in cases where i ≤ j.

2. Recurrence Relation (State Transition)

The state isPalindrome[i][j] depends on whether the characters at its ends match, and if so, whether its inner substring is also a palindrome.

• If s[i] != s[j], then s[i...j] cannot be a palindrome. Thus, isPalindrome[i][j] = false.
• If s[i] == s[j], we have three sub-cases:
  1. If the substring s[i...j] has a length of 1 (i.e., i == j), it is a palindrome. So, isPalindrome[i][j] = true.
  2. If the substring s[i...j] has a length of 2 (i.e., j == i + 1), and s[i] == s[j], it is a palindrome. So, isPalindrome[i][j] = true.
  3. If the substring s[i...j] has a length greater than 2 (i.e., j > i + 1), its palindromic nature depends on whether the inner substring s[i+1...j-1] is also a palindrome. So, isPalindrome[i][j] = isPalindrome[i+1][j-1].

These conditions can be concisely combined:

if (s[i] == s[j]) {
    if (j - i < 2) { // Handles length 1 (i==j) and length 2 (j==i+1)
        isPalindrome[i][j] = true;
    } else { // Handles length > 2
        isPalindrome[i][j] = isPalindrome[i+1][j-1];
    }
} else {
    isPalindrome[i][j] = false;
}

3. Initialization and Traversal Order

No explicit initialization is needed beyond the default false for boolean arrays, as the base cases (length 1 and 2) are handled by the recurrence relation. However, the traversal order is crucial. To compute isPalindrome[i][j], we might need isPalindrome[i+1][j-1]. This implies we should compute shorter substrings before longer ones, or substrings where the start index is greater and the end index is smaller.

A common traversal order is to iterate i from stringLength - 1 down to 0, and j from i up to stringLength - 1. This ensures that when isPalindrome[i+1][j-1] is accessed, it has already been computed.

4. Result Accumulation

We need to count how many substrings are palindromes. A counter variable should be incremented every time isPalindrome[i][j] is determined to be true.

C++ Implementation for Counting Palindromic Substrings

class Solution {
public:
    int countSubstrings(std::string s) {
        int stringLength = s.length();
        if (stringLength == 0) {
            return 0;
        }

        std::vector<std::vector<bool>> isPalindrome(stringLength, std::vector<bool>(stringLength, false));
        int totalPalindromeCount = 0;

        // Iterate backward for 'i' and forward for 'j' to ensure inner states are computed first
        for (int i = stringLength - 1; i >= 0; --i) {
            for (int j = i; j < stringLength; ++j) {
                if (s[i] == s[j]) {
                    // Base cases: single character (i==j) or two characters (j==i+1)
                    if (j - i < 2) { 
                        isPalindrome[i][j] = true;
                    } else { // General case: depends on the inner substring
                        isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
                    }
                }
                
                if (isPalindrome[i][j]) {
                    totalPalindromeCount++;
                }
            }
        }
        return totalPalindromeCount;
    }
};

The time and space complexity for this approach are both O(N^2), where N is the length of the string.

Finding the Longest Palindromic Substring

This section details how to find the longest palindromic substring within a given string, aligning with LeetCode problem 5.

Problem Description

Given a string s, identify and return the longest palindromic substring within it. A string is a palindrome if it reads the same forwards and backwards.

Dynamic Programming Approach

The core logic for determining if a substring is a palindrome remains the same as in the previous problem. The difference lies in how we extract the final result: instead of counting, we track the longest palindrome encountered.

1. State Definition

Identical to the prveious problem: isPalindrome[i][j] is a boolean indicating whether s[i...j] is a palindrome.

2. Recurrence Relation (State Transition)

The recurrence relation is also identical:

if (s[i] == s[j]) {
    if (j - i < 2) { // Handles length 1 (i==j) and length 2 (j==i+1)
        isPalindrome[i][j] = true;
    } else { // Handles length > 2
        isPalindrome[i][j] = isPalindrome[i+1][j-1];
    }
} else {
    isPalindrome[i][j] = false;
}

3. Initialization and Traversal Order

The traversal order remains the same: iterate i from stringLength - 1 down to 0, and j from i up to stringLength - 1 to ensure proper dependency resolution.

4. Result Extraction

During the DP table filling, whenever isPalindrome[i][j] is found to be true, we calculate the current substring's length (j - i + 1). If this length is greater than the maximum length recorded so far, we update our maximum length and store the corresponding starting index i. After filling the antire table, we use the stored starting index and maximum length to extract the longest palindromic substring from the original string.

C++ Implementation for Longest Palindromic Substring

class Solution {
public:
    std::string longestPalindrome(std::string s) {
        int stringLength = s.length();
        if (stringLength < 2) {
            return s;
        }

        std::vector<std::vector<bool>> isPalindrome(stringLength, std::vector<bool>(stringLength, false));
        
        int longestSubstrStart = 0;
        int maxLen = 1; // Minimum possible length for a non-empty string is 1

        for (int i = stringLength - 1; i >= 0; --i) {
            for (int j = i; j < stringLength; ++j) {
                if (s[i] == s[j]) {
                    if (j - i < 2) { // Single character or two matching characters
                        isPalindrome[i][j] = true;
                    } else { // Check inner substring
                        isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
                    }
                }

                // If s[i...j] is a palindrome and longer than current max
                if (isPalindrome[i][j] && (j - i + 1 > maxLen)) {
                    maxLen = j - i + 1;
                    longestSubstrStart = i;
                }
            }
        }
        return s.substr(longestSubstrStart, maxLen);
    }
};

The time and space complexity remain O(N^2), where N is the length of the string.

Partitioning into Three Palindromic Substrings

This section addresses the problem of determining if a string can be partitioned into three non-empty palindromic substrings, similar to LeetCode problem 1745.

Problem Description

Given a string s, return true if it can be split into three non-empty palindromic substrings; otherwise, return false.

Algorithm Principle

This problem also relies on efficiently checking if any substring is a palindrome. We can precompute all palindromic substrings using dynamic programming, then iterate through all possible ways to make two cuts to divide the string into three parts. For each partition, we check if all three resulting substrings are palindromes.

1. Precomputing Palindromes (State Definition, Recurrence, Traversal)

The initial step is to build the same isPalindrome[i][j] table as described in the previous problems, indicating whether s[i...j] is a palindrome. The state definition, recurrence relation, and traversal order for populating this table are identical.

// Example for precomputation
std::vector<std::vector<bool>> isPalindrome(stringLength, std::vector<bool>(stringLength, false));
for (int i = stringLength - 1; i >= 0; --i) {
    for (int j = i; j < stringLength; ++j) {
        if (s[i] == s[j]) {
            if (j - i < 2) {
                isPalindrome[i][j] = true;
            } else {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
            }
        }
    }
}

2. Enumerating Partitions

Once the isPalindrome table is populated, we need to find two cut points. Let the string be s of length N. We need to find indices k1 and k2 such that:

• 0 ≤ k1 < k2 < N - 1 (ensures three non-empty parts)
• The first part is s[0...k1]
• The second part is s[k1+1...k2]
• The third part is s[k2+1...N-1]

We can iterate k1 from 0 up to N-3 (ensuring at least two characters remain for the next two parts). Then, iterate k2 from k1+1 up to N-2 (ensuring at least one character remains for the third part).

For each pair of (k1, k2), we check if isPalindrome[0][k1], isPalindrome[k1+1][k2], and isPalindrome[k2+1][N-1] are all true. If so, we've found a valid partition and can immediately return true. If no such partition is found after checking all possibilities, we return false.

C++ Implementation for Partitioning into Three Palindromic Substrings

class Solution {
public:
    bool checkPartitioning(std::string s) {
        int stringLength = s.length();
        if (stringLength < 3) { // Must have at least 3 characters for 3 non-empty substrings
            return false;
        }

        // Step 1: Precompute all palindromic substrings
        std::vector<std::vector<bool>> isPalindrome(stringLength, std::vector<bool>(stringLength, false));
        for (int i = stringLength - 1; i >= 0; --i) {
            for (int j = i; j < stringLength; ++j) {
                if (s[i] == s[j]) {
                    if (j - i < 2) {
                        isPalindrome[i][j] = true;
                    } else {
                        isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
                    }
                }
            }
        }
        
        // Step 2: Iterate through all possible cut points for three non-empty parts
        // First cut: divides s[0...k1] and s[k1+1...N-1]
        // k1 goes from 0 to N-3 (at least 2 chars remain for part 2 and 3)
        for (int k1 = 0; k1 < stringLength - 2; ++k1) {
            // Second cut: divides s[k1+1...k2] and s[k2+1...N-1]
            // k2 goes from k1+1 to N-2 (at least 1 char remains for part 3)
            for (int k2 = k1 + 1; k2 < stringLength - 1; ++k2) {
                // Check if all three parts are palindromes
                if (isPalindrome[0][k1] &&        // First part: s[0...k1]
                    isPalindrome[k1 + 1][k2] &&    // Second part: s[k1+1...k2]
                    isPalindrome[k2 + 1][stringLength - 1]) { // Third part: s[k2+1...N-1]
                    return true;
                }
            }
        }
        
        return false;
    }
};

The time complexity for precomputing the palindromes is O(N^2). The subsequent iteration for finding cut points is also O(N^2) (nested loops up to N). Thus, the overall time complexity is O(N^2). The space complexity is O(N^2) for the isPalindrome table.