Palindromic Substrings medium

Problem Statement

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

A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Steps

The approach we'll use is based on expanding around the center. We iterate through each character (and between each character pair) as a potential center of a palindrome. From each center, we expand outwards, checking if characters are equal. We increment a counter each time we find a palindrome.

Explanation

1. Initialization: We initialize a count variable to 0 to store the number of palindromic substrings.

2. Iterating through centers: We iterate through the string using a for loop. Each character is considered a potential center of an odd-length palindrome. We also iterate between each character pair to consider potential centers of even-length palindromes.

3. Expanding around the center: For each potential center, we use two pointers, left and right, to expand outwards. We check if the characters at left and right are equal. If they are, we increment count and continue expanding. If they are not equal, we stop expanding for that center.

4. Updating count: Every time we find a palindrome, we increment the count.

Code

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            count += expandAroundCenter(s, i, i);

            // Even length palindromes
            count += expandAroundCenter(s, i, i + 1);
        }

        return count;
    }

    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

Complexity

• Time Complexity: O(n^2), where n is the length of the string. This is because in the worst case (e.g., "aaaa..."), we might expand around each center for a significant portion of the string.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.