Palindromic Substrings

7
0

Problem Statement

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

A palindrome reads the same from left to right and from right to left. A substring is a continuous part of a string. Count each occurrence separately, even when two substrings contain the same characters.

Example 1

Input: s = "aba"
Output: 4
Explanation: The palindromic substrings are "a" at index 0, "b" at index 1, "a" at index 2, and "aba".

Example 2

Input: s = "abaa"
Output: 6
Explanation: The palindromic substrings are "a" (at indices 0, 2, and 3), "b" (at index 1), "aa" (at indices 2–3), and "aba" (at indices 0–2).

Brute Force Approach

The problem can be solved by checking every possible substring of the s. Choose its starting and ending positions, then compare the characters at both ends. If they match, move inward and check the next pair. A mismatch means the substring is not a palindrome.

When the pointers meet or cross without finding a mismatch, the substring is a palindrome and adds one to the answer. Every non-empty substring has one unique pair of boundaries, so visiting all these pairs counts every occurrence exactly once.

Algorithm

  • Initialize count to zero and store the length of the string in n.

  • Use an outer loop to select each possible starting index, beginning at the first character and ending at the last character.

  • For each starting index, use an inner loop to select every possible ending index, beginning at the current starting index and continuing to the last character. This ensures that all valid, non-empty substrings are considered exactly once.

  • Pass the original string and the selected starting and ending indices to a helper function that checks whether the substring is a palindrome.

  • Inside the helper function, keep comparing characters as long as the left index is smaller than the right index. Stop when both indices meet or cross.

  • If the characters at the left and right indices do not match, return false immediately. Otherwise, move the left index one position forward and the right index one position backward.

  • If all compared character pairs match, return true. Increase count by one for every substring confirmed to be a palindrome.

  • After checking all possible starting and ending index pairs, return count as the total number of palindromic substrings.

Dry Run

Palindromic Substrings - Brute Force

Palindromic Substrings - Brute Force

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks whether the substring s[left..right] is a palindrome.
bool isPalindrome(const string& s, int left, int right) {
// Stop at the middle; a single remaining character always matches itself.
while (left < right) {
if (s[left] != s[right]) {
return false;
}
// The outer pair matches, so check the next pair inside it.
++left;
--right;
}
return true;
}
// Counts all palindromic substrings in s by testing every [start, end] range.
int countSubstrings(string s) {
// Passing this string by value copies its N characters for this call.
int n = s.size();
int count = 0;
for (int start = 0; start < n; ++start) {
// end starts at start, so every chosen substring is non-empty.
for (int end = start; end < n; ++end) {
// Check the original range directly without making a substring.
if (isPalindrome(s, start, end)) {
++count;
}
}
}
return count;
}
};
// Driver code
int main() {
string s = "abaa";
Solution sol;
cout << sol.countSubstrings(s) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N³), where N is the length of s. There are N x (N + 1)/2 substrings, and checking one can take O(N) time.

Space Complexity: O(1) for the counting procedure. It uses only counters and two pointers, and it checks ranges in the original string without creating substring copies.

Optimal Approach

The brute force method repeats many comparisons across overlapping substrings. The problem can be solve optimally by starting at the middle of a palindrome and growing it outward.

An odd-length palindrome has one middle character, while an even-length palindrome has a gap in the middle. For example, "aba" grows around "b", and "aa" grows around the gap between its two characters.

For each center, move a left pointer and a right pointer outward while the characters match. Each successful match gives one palindrome: the substring between those pointers. Once a mismatch appears, expanding farther from that center cannot form a palindrome because the mismatched pair would remain inside it. Every palindromic occurrence has exactly one center, so checking both kinds of centers counts it once.

Algorithm

  • Initialize count to zero and let n represent the length of the string.

  • Visit every index of the string from the first to the last, treating each index as the center.

  • For odd-length palindromes, place both the left and right pointers at the current center.

  • Keep expanding outward as long as both pointers remain within the string and the characters at their positions match. For every successful match, increase the local count by one, move the left pointer one position backward, and move the right pointer one position forward.

  • Stop expanding when the characters do not match or either pointer moves outside the string. Add the local count to count.

  • For even-length palindromes, repeat the same process, but place the left pointer at the current center and the right pointer at the next position.

  • After checking both odd-length and even-length palindromes for every center, return count as the total number of palindromic substrings.

Dry Run

Palindromic Substrings - Center Expansion

Palindromic Substrings - Center Expansion

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Expands outward from [left, right] and returns how many palindromes share this center.
int expandFromCenter(const string& s, int left, int right) {
int n = s.size();
int palindromes = 0;
// Check bounds before reading characters; stop at the first mismatch.
while (left >= 0 && right < n && s[left] == s[right]) {
// This matching range adds one palindrome for this center.
++palindromes;
--left;
++right;
}
return palindromes;
}
// Counts all palindromic substrings by checking odd and even centers at every index.
int countSubstrings(string s) {
// Passing this string by value copies its N characters for this call.
int n = s.size();
int count = 0;
for (int center = 0; center < n; ++center) {
// One middle character gives odd lengths; a gap gives even lengths.
count += expandFromCenter(s, center, center);
count += expandFromCenter(s, center, center + 1);
// At the last center, the even call stops immediately at right == n.
}
return count;
}
};
// Driver code
int main() {
string s = "abaa";
Solution sol;
cout << sol.countSubstrings(s) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N is the length of s. There are O(N) centers, and a center can take O(N) comparisons.

Space Complexity: O(1), as we don't use any extra space apart from a few variables.

Interview follow-up Questions

The largest count is N x (N + 1)/2, reached when all characters are the same. Every non-empty substring is then a palindrome.

StringTCS NQT

Read Similar Blogs

Comments0