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.
1function countSubstrings(s) {
2 let count = 0;
3 const n = s.length;
4 for (let center = 0; center < 2 * n - 1; ++center) {
5 let left = Math.floor(center / 2);
6 let right = left + center % 2;
7 while (left >= 0 && right < n && s[left] === s[right]) {
8 count++;
9 left--;
10 right++;
11 }
12 }
13 return count;
14}
15
16const s = "aaa";
17console.log(countSubstrings(s)); // Output: 6This JavaScript solution utilizes a similar approach, checking each character and each pair of characters as the center of potential palindromes, expanding outward until a mismatch is identified.
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.
1def count_substrings(s: str) -> int:
2 n = len(s)
3 dp = [[False] * n for _ in range(n)]
4 count = 0
5 for i in range(n - 1, -1, -1):
6 for j in range(i, n):
7 dp[i][j] = (s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1]))
8 if dp[i][j]:
9 count += 1
10 return count
11
12s = "aaa"
13print(count_substrings(s)) # Output: 6This Python solution uses a similar DP table to store whether substrings are palindromes and iteratively build solutions for larger substrings based on these results.