Definition
- Counting variant of the longest palindromic substring problem, counting instead of tracking the maximum.
- Unique center and radius ensures each palindromic substring is produced by exactly one center at one expansion step, preventing double counting.
- Expand helper returns the number of successful expansion steps from a given center, not the length.
- Minimum count is n (every single character is a palindrome) and maximum count is n(n+1)/2 for a string of all identical characters.
- O(n squared) time and O(1) space using the expand-around-center approach.
The National Bank of India measures how much symmetric structure a batch file identifier contains by counting every symmetric fragment inside it. More overlapping symmetric fragments suggest a machine-generated identifier worth flagging. Standing at every center, each time you push outward and the two sides still match, that is one more palindrome to tally.
Understanding the Concepts
What is the problem?
Given a string, count how many contiguous substrings are palindromes. Different positions count separately even if the text is identical. For "aaa", the answer is 6: three single-character palindromes ("a", "a", "a"), two two-character palindromes ("aa", "aa"), and one three-character palindrome ("aaa").
package com.bank.dsa;
public class PalindromicSubstringsCount {
public static int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
count += expandCount(s, i, i); // odd centers
count += expandCount(s, i, i + 1); // even centers
}
return count;
}
private static int expandCount(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;
}
}
Why does this matter in banking?
At the National Bank of India, the security team computes a symmetry score for batch file identifiers. A high count of palindromic substrings indicates a highly structured, likely machine-generated identifier. Rajesh flags identifiers where the palindrome count exceeds a threshold relative to the string length.
package com.bank.service;
import com.bank.dsa.PalindromicSubstringsCount;
public class IdentifierScoringService {
public void score(String identifier) {
int count = PalindromicSubstringsCount.countSubstrings(identifier);
double ratio = (double) count / identifier.length();
System.out.println("Identifier: " + identifier);
System.out.println("Palindrome count: " + count + ", ratio: " + String.format("%.2f", ratio));
if (ratio > 3.0) {
System.out.println("WARNING: Likely machine-generated");
}
}
public static void main(String[] args) {
new IdentifierScoringService().score("ABCBA");
new IdentifierScoringService().score("AAAA");
}
}
Identifier: ABCBA
Palindrome count: 7, ratio: 1.40
Identifier: AAAA
Palindrome count: 10, ratio: 2.50
How does counting differ from finding the longest?
The longest palindrome problem tracks the single best span. The counting problem sums one palindrome for each successful expansion step at every center. The expand helper returns a count instead of a length. Everything else is identical.
package com.bank.dsa;
public class CountVsLongestDemo {
public static void main(String[] args) {
String s = "ABCBA";
// Counting: sum all successful expansions
int totalCount = PalindromicSubstringsCount.countSubstrings(s);
// Longest: track max length
String longest = LongestPalindromicSubstring.longestPalindrome(s);
System.out.println("Total palindromes: " + totalCount);
System.out.println("Longest palindrome: " + longest);
}
}
Total palindromes: 7
Longest palindrome: ABCBA
Why is there no double counting?
Every palindromic substring has a unique center (a specific character or gap) and a unique radius (how far it extends from that center). An odd-length palindrome comes from a character center, an even-length one from a gap center, and the expansion radius pins down its exact span. So each palindrome is produced by exactly one center at exactly one expansion step.
package com.bank.dsa;
public class NoDuplicateDemo {
public static void main(String[] args) {
String s = "ABA";
// Center 0 (A): expand(0,0) finds "A" ── count 1
// Center 1 (B): expand(1,1) finds "B" then "ABA" ── count 2
// Center 2 (A): expand(2,2) finds "A" ── count 1
// Even centers: none match
// Total: 4 (A, B, A, ABA) ── each counted exactly once
System.out.println("Count: " + PalindromicSubstringsCount.countSubstrings(s));
}
}
Count: 4
What is the time and space complexity?
Time is O(n squared) because there are O(n) centers and each expansion can take O(n) steps. Space is O(1) because only a counter and loop variables are used. The worst case is a string of all identical characters where the total number of palindromic substrings is n(n+1)/2, which is quadratic, so even just counting them requires quadratic time.
package com.bank.dsa;
public class ComplexityDemo {
public static void main(String[] args) {
// Worst case: all identical, n(n+1)/2 palindromes
int n = 5;
String s = "A".repeat(n);
int count = PalindromicSubstringsCount.countSubstrings(s);
int expected = n * (n + 1) / 2;
System.out.println("n=" + n + " count=" + count + " expected=" + expected);
}
}
n=5 count=15 expected=15
What are the edge cases?
A single character has exactly 1 palindromic substring. An empty string has 0. Two identical characters have 3 palindromes (two singles and one pair). Two different characters have 2 palindromes (just the two singles).
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println("Single: " + PalindromicSubstringsCount.countSubstrings("A")); // 1
System.out.println("Empty: " + PalindromicSubstringsCount.countSubstrings("")); // 0
System.out.println("AA: " + PalindromicSubstringsCount.countSubstrings("AA")); // 3
System.out.println("AB: " + PalindromicSubstringsCount.countSubstrings("AB")); // 2
}
}
Single: 1
Empty: 0
AA: 3
AB: 2
What about Manacher's algorithm for counting?
Manacher's algorithm computes the palindrome radius at each center in O(n) time. Summing these radii gives the total palindrome count in O(n) total time. This is optimal for counting only, though enumerating all palindromic substrings remains quadratic because there can be that many.
What are common mistakes?
The first mistake is forgetting the even centers, which misses all even-length palindromes. The second mistake is returning a count that includes empty substrings. The third mistake is confusing the expand helper that returns a count with one that returns a length.
package com.bank.dsa;
public class CommonMistakesDemo {
// WRONG: only odd centers, misses even palindromes
public static int buggyCount(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
int l = i, r = i;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
count++;
l--; r++;
}
// Missing: expand(i, i+1) for even centers
}
return count;
}
public static void main(String[] args) {
System.out.println("Buggy AA: " + buggyCount("AA")); // 2 (misses "AA")
System.out.println("Correct AA: " + PalindromicSubstringsCount.countSubstrings("AA")); // 3
}
}
Buggy AA: 2
Correct AA: 3
What are common interview follow-up questions?
- How would you find the longest palindromic substring instead of counting?
- Can you count distinct palindromic substrings using a suffix array or Eertree?
- How would you count palindromic subsequences instead of substrings?
- What is the relationship between palindrome count and string entropy?
Visual Overview
Input: "ABA"
Odd centers:
Center 0 (A): expand(0,0)
step 1: s[0]='A' == s[0]='A' ── count++ (palindrome: "A")
step 2: out of bounds ── stop
subtotal: 1
Center 1 (B): expand(1,1)
step 1: s[1]='B' == s[1]='B' ── count++ (palindrome: "B")
step 2: s[0]='A' == s[2]='A' ── count++ (palindrome: "ABA")
step 3: out of bounds ── stop
subtotal: 2
Center 2 (A): expand(2,2)
step 1: s[2]='A' == s[2]='A' ── count++ (palindrome: "A")
subtotal: 1
Even centers: all fail (A!=B, B!=A)
subtotal: 0
Total: 1 + 2 + 1 + 0 = 4
Palindromes: "A", "B", "A", "ABA"
Key Takeaway
The Palindromic Substrings counting problem is the counting cousin of the longest palindromic substring, and it uses the same expand-around-center machinery. Instead of tracking the single longest span, you count one palindrome for each successful outward expansion step at every center. The expand helper returns a count rather than a length, and the total accumulates across all 2n-1 centers.
The reason there is no double counting is that every palindromic substring has a unique center and a unique radius. An odd-length palindrome comes from a character center and an even-length one from a gap center. The expansion radius pins down the exact span. So summing one per successful expansion over all centers counts each palindrome exactly once by position.
At the National Bank of India, Rajesh uses this as a symmetry score for batch file identifiers. A high ratio of palindrome count to string length suggests a machine-generated identifier rather than a human-assigned one. The algorithm runs in O(n squared) time with O(1) space, and the worst case of all identical characters produces n(n+1)/2 palindromes, which is inherently quadratic to even enumerate.
Manacher's algorithm can compute per-center radii in O(n) time and sum them for the total count, making it optimal for counting only. But in an interview, the expand-around-center approach is the standard expectation, and mentioning Manacher's as the linear optimization is a strong follow-up.
Remember one sentence: expand from every center, count one palindrome per successful expansion step, and the unique center-radius pair guarantees no double counting.
---