Palindromic Substrings medium

Problem Statement

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

A substring is a contiguous sequence of characters within a 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 and Explanation

The core idea is to iterate through the string and for each character, expand outwards to check for palindromes of odd and even lengths. We use a counter to keep track of the total number of palindromic substrings.

1. Initialization: Initialize a counter count to 0. This will store the total number of palindromic substrings.

2. Iteration: Iterate through each character of the string s using a for loop.

3. Odd Length Palindromes: For each character, consider it as the center of a potential odd-length palindrome. Expand outwards from the center, comparing characters to check if it's a palindrome. Increment count if a palindrome is found.

4. Even Length Palindromes: Similarly, consider each pair of adjacent characters as the center of a potential even-length palindrome. Expand outwards and check for palindromes, incrementing count accordingly.

5. Return: After iterating through the entire string, return the final count.

Code (C#)

public class Solution {
    public int CountSubstrings(string s) {
        int count = 0;
        int n = s.Length;

        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]) {
                count++;
                l--;
                r++;
            }

            // Even length palindromes
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                count++;
                l--;
                r++;
            }
        }
        return count;
    }
}

Complexity Analysis

• Time Complexity: O(n^2), where n is the length of the string. This is because we expand outwards from each character, potentially checking up to n characters in each direction.

• Space Complexity: O(1). The algorithm uses only a constant amount of extra space. The space used is independent of the input size.