In this approach, consider each character in the string, and each pair of consecutive characters as the center of potential palindromes. From each center, expand outward until the substring is no longer a palindrome. This allows for both odd-length and even-length palindromes to be discovered.
Time complexity: O(n^2), where n is the length of the string.
Space complexity: O(1), since we're only using a few auxiliary variables.
1using System;
2
3public class PalindromeSubstrings {
4 public static int CountSubstrings(string s) {
5 int count = 0, n = s.Length;
6 for (int center = 0; center < 2 * n - 1; ++center) {
7 int left = center / 2;
8 int right = left + center % 2;
9 while (left >= 0 && right < n && s[left] == s[right]) {
10 count++;
11 left--;
12 right++;
13 }
14 }
15 return count;
16 }
17
18 public static void Main() {
19 string s = "aaa";
20 Console.WriteLine(CountSubstrings(s)); // Output: 6
21 }
22}
The C# method expands around possible centers to detect all palindromic substrings, efficiently traversing the string within the constraints.
Utilizing Dynamic Programming, we can store results of previously calculated palindromic substrings in a table. If we know a substring between two indices is a palindrome, we can extend this information to build larger palindromes, reducing redundant checks.
Time complexity: O(n^2), Space complexity: O(n^2), due to the storage of the DP table.
1#include <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4
5int countSubstrings(char *s) {
6 int n = strlen(s);
7 bool dp[n][n];
8 int count = 0;
9 for (int i = n - 1; i >= 0; i--) {
10 for (int j = i; j < n; j++) {
11 dp[i][j] = (s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1]));
12 if (dp[i][j]) {
13 count++;
14 }
15 }
16 }
17 return count;
18}
19
20int main() {
21 char s[] = "aaa";
22 printf("%d\n", countSubstrings(s)); // Output: 6
23 return 0;
24}
This C solution fills a DP table where dp[i][j] is true if the substring s[i..j] is a palindrome, using known results of smaller substrings to build the solution for larger substrings.