Count Palindromic Substrings

Given a string str, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same from back and front. A substring is a contiguous sequence of characters within the string.

Example

String s1 = "abc";  // Output: 3

Palindromic strings: "a", "b", "c".

String s2 = "aaa";  // Output: 6

Palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Approach

Manacher's algorithm is an efficient algorithm used to find the number of palindromic substrings in a given string in linear time, O(n). It was originally developed for finding the longest palindromic substring but can also be adapted to count palindromic substrings.

Idea

Manacher's algorithm efficiently counts palindromic substrings in linear time by inserting a unique character between each pair of characters in the string. It maintains a center and right boundary while iterating through the modified string. The algorithm dynamically calculates the mirror position relative to the current center, efficiently expanding palindromes and counting them as it iterates through the string. This approach allows Manacher's algorithm to achieve a time complexity of O(n) for counting palindromic substrings.

Algorithm

1. Insert a unique character between each character and at the beginning and end of the string to handle even and odd-length palindromes.
2. Initialize variables: center to 0, right to 0, and count to 0.
3. For each character in the modified string:
   1. Calculate the mirror position relative to the current centre.
   2. If the current position is within the right boundary:
      1. Initialize the palindrome length (p[i]) based on previously computed values, using the minimum of the right boundary and the mirror value.
   3. Expand the palindrome by comparing characters and updating p[i].
   4. If the expanded palindrome extends beyond the right boundary, update the centre and right.
   5. Count the newly found palindromes.
4. The count represents the number of palindromic substrings in the original string.

Complexity

• Time Complexity: O(n), where 'n' is the length of the input string
• Space Complexity: O(n), where 'n' is the length of the input string

Java Code

public class PalindromicSubstrings {
    public int countSubstrings(String input) {
        StringBuilder modifiedString = new StringBuilder("#");
        for (char character : input.toCharArray()) {
            modifiedString.append(character).append('#');
        }
        int length = modifiedString.length();
        int[] palindromeLengths = new int[length];
        int center = 0, rightBoundary = 0, palindromeCount = 0;

        for (int currentIndex = 0; currentIndex < length; currentIndex++) {
            int mirrorIndex = 2 * center - currentIndex;

            if (currentIndex < rightBoundary) {
                palindromeLengths[currentIndex] = Math.min(rightBoundary - currentIndex, palindromeLengths[mirrorIndex]);
            }

            int expandRight = currentIndex + (1 + palindromeLengths[currentIndex]);
            int expandLeft = currentIndex - (1 + palindromeLengths[currentIndex]);

            while (expandRight < length && expandLeft >= 0 && modifiedString.charAt(expandRight) == modifiedString.charAt(expandLeft)) {
                palindromeLengths[currentIndex]++;
                expandRight++;
                expandLeft--;
            }

            if (currentIndex + palindromeLengths[currentIndex] > rightBoundary) {
                center = currentIndex;
                rightBoundary = currentIndex + palindromeLengths[currentIndex];
            }

            palindromeCount += (palindromeLengths[currentIndex] + 1) / 2;
        }

        return palindromeCount;
    }

    public static void main(String[] args) {
        PalindromicSubstrings solution = new PalindromicSubstrings();
        String input = "aaa";
        int count = solution.countSubstrings(input);
        System.out.println("Number of palindromic substrings of the string " + input + " : " + count);
    }
}

Output

Number of palindromic substrings of the string aaa : 6