Definition
- Palindrome center can be a single character (odd-length) or a gap between two characters (even-length), giving 2n-1 possible centers.
- Expand-around-center starts at each center and pushes outward one step at a time while the characters on both sides match and stay in bounds.
- O(n squared) time comes from a linear number of centers each potentially expanding to linear length.
- O(1) space is achieved by only tracking the start and length of the best span, without building extra structures.
- Manacher's algorithm is the O(n) alternative that reuses palindrome radii, mentioned as a follow-up rather than the default.
The National Bank of India scans reference strings for suspicious symmetric patterns. The idea is to stand at every possible center of the string, both on a character and between two characters, and push outward one step at a time as long as the characters on both sides keep matching. Whichever center produces the widest mirror wins.
Understanding the Concepts
What is the problem?
Given a string, find the longest contiguous substring that reads the same forward and backward. For "babad", the answer is "bab" or "aba" (both length 3). This is one of the most popular string problems in coding interviews.
package com.bank.dsa;
public class LongestPalindromicSubstring {
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int oddLen = expand(s, i, i);
int evenLen = expand(s, i, i + 1);
int len = Math.max(oddLen, evenLen);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private static int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
Why does this matter in banking?
The National Bank of India's fraud detection team flags reference strings containing unusually long symmetric segments, because machine-generated identifiers often have palindromic patterns. Rajesh runs expand-around-center on reference fields to measure the longest symmetric run and flags identifiers exceeding a threshold.
package com.bank.service;
import com.bank.dsa.LongestPalindromicSubstring;
public class FraudDetectionService {
private static final int SUSPICIOUS_LENGTH = 5;
public void checkReference(String reference) {
String palindrome = LongestPalindromicSubstring.longestPalindrome(reference);
System.out.println("Reference: " + reference);
System.out.println("Longest palindrome: '" + palindrome + "' (length " + palindrome.length() + ")");
if (palindrome.length() >= SUSPICIOUS_LENGTH) {
System.out.println("WARNING: Suspicious symmetric pattern detected");
}
}
public static void main(String[] args) {
new FraudDetectionService().checkReference("TXN1ABCBA99");
new FraudDetectionService().checkReference("TXN2XY789");
}
}
Reference: TXN1ABCBA99
Longest palindrome: 'ABCBA' (length 5)
WARNING: Suspicious symmetric pattern detected
Reference: TXN2XY789
Longest palindrome: 'T' (length 1)
How does expand-around-center work?
A palindrome is defined by its center and symmetric expansion. An odd-length palindrome has a single character at its center. An even-length palindrome has its center between two characters. For a string of length n, there are 2n-1 possible centers. The algorithm tries each center and expands outward.
package com.bank.dsa;
public class ExpandDemo {
public static void main(String[] args) {
String s = "ABCBA";
// Odd center at index 2 ('C')
int left = 2, right = 2;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
System.out.println("Match: s[" + left + "]='" + s.charAt(left)
+ "' == s[" + right + "]='" + s.charAt(right) + "'");
left--;
right++;
}
System.out.println("Palindrome: " + s.substring(left + 1, right));
}
}
Match: s[2]='C' == s[2]='C'
Match: s[1]='B' == s[3]='B'
Match: s[0]='A' == s[4]='A'
Palindrome: ABCBA
How do you handle both odd and even centers?
A helper method takes a left and right starting index. For odd centers, pass (i, i). For even centers, pass (i, i+1). The helper expands while both sides match and returns the palindrome length. This avoids code duplication.
package com.bank.dsa;
public class BothCentersDemo {
private static int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
public static void main(String[] args) {
String s = "AABB";
for (int i = 0; i < s.length(); i++) {
int odd = expand(s, i, i);
int even = expand(s, i, i + 1);
System.out.println("Center " + i + ": odd=" + odd + " even=" + even);
}
}
}
Center 0: odd=1 even=2
Center 1: odd=1 even=0
Center 2: odd=1 even=2
Center 3: odd=1 even=0
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) time in the worst case (a string of all identical characters). Space is O(1) because only the start and end indices of the best palindrome are tracked. This is the expected interview solution.
What are the edge cases?
An empty string returns an empty string. A single character is itself a palindrome. A string of all identical characters like "AAAA" has the entire string as its longest palindrome. A string with no palindrome longer than 1 returns any single character.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println("Empty: '" + LongestPalindromicSubstring.longestPalindrome("") + "'");
System.out.println("Single: '" + LongestPalindromicSubstring.longestPalindrome("A") + "'");
System.out.println("All same: '" + LongestPalindromicSubstring.longestPalindrome("AAAA") + "'");
System.out.println("No long: '" + LongestPalindromicSubstring.longestPalindrome("ABCD") + "'");
}
}
Empty: ''
Single: 'A'
All same: 'AAAA'
No long: 'A'
What are common mistakes?
The most common bug is getting the start and end index arithmetic wrong when converting from center and length back to substring indices. The even-center case is especially tricky. The formula start = i - (len - 1) / 2 and end = i + len / 2 handles both parities correctly.
package com.bank.dsa;
public class ArithmeticDemo {
public static void main(String[] args) {
// For center i=2, odd length=5: start=2-(5-1)/2=0, end=2+5/2=4
int i = 2, len = 5;
int start = i - (len - 1) / 2;
int end = i + len / 2;
System.out.println("Center=" + i + " len=" + len + " start=" + start + " end=" + end);
// For center i=1, even length=2: start=1-(2-1)/2=1, end=1+2/2=2
i = 1; len = 2;
start = i - (len - 1) / 2;
end = i + len / 2;
System.out.println("Center=" + i + " len=" + len + " start=" + start + " end=" + end);
}
}
Center=2 len=5 start=0 end=4
Center=1 len=2 start=1 end=2
What about Manacher's algorithm?
Manacher's algorithm reaches O(n) time by transforming the string with separator characters and reusing previously computed palindrome radii via a mirror property around the current rightmost palindrome boundary. It is rarely required to code live in an interview, but mentioning it shows awareness of the optimal solution.
package com.bank.dsa;
public class ManacherNote {
// Manacher's transforms "ABC" into "#A#B#C#" to unify odd/even centers
// Then uses mirror property: if a center is within a known palindrome,
// its radius is at least the mirror's radius.
// Full implementation is ~30 lines but error-prone under interview pressure.
public static void main(String[] args) {
String s = "ABC";
StringBuilder transformed = new StringBuilder("#");
for (char c : s.toCharArray()) {
transformed.append(c).append('#');
}
System.out.println("Original: " + s);
System.out.println("Transformed: " + transformed);
}
}
Original: ABC
Transformed: #A#B#C#
What are common interview follow-up questions?
- How would you count all palindromic substrings instead of finding the longest?
- Can you solve this with dynamic programming and what are the trade-offs?
- How does Manacher's algorithm achieve linear time?
- How would you find the longest palindromic subsequence (not substring)?
Visual Overview
Input: "BABAD" Centers (2n-1 = 9): Index: 0 1 2 3 4 Char: B A B A D Odd centers: B A B A D (5 centers) Even centers: BA AB BA AD (4 centers) Center i=0 (B): expand(0,0) = 1 Center i=1 (A): expand(1,1) = 3 ── "BAB" Center i=2 (B): expand(2,2) = 3 ── "ABA" Center i=3 (A): expand(3,3) = 1 Center i=4 (D): expand(4,4) = 1 Even centers all give 0 or 0 Best = 3, start=0, substring = "BAB" ┌──────────────────────────────────┐ │ Expand Around Center │ │ │ │ For each i in 0..n-1: │ │ odd = expand(i, i) │ │ even = expand(i, i+1) │ │ len = max(odd, even) │ │ update best if len > current │ └──────────────────────────────────┘
Key Takeaway
The Longest Palindromic Substring is one of the most frequently asked string problems in coding interviews. The expand-around-center approach is the expected solution: for each of the 2n-1 possible centers, expand outward while the characters on both sides match and stay in bounds, tracking the longest span found. This runs in O(n squared) time with O(1) extra space.
Rajesh at the National Bank of India uses this in a fraud detection utility that flags reference strings containing unusually long symmetric segments. The algorithm handles both odd-length palindromes centered on a single character and even-length palindromes centered between two characters using a single helper method that takes left and right start indices.
The most common bug is the index arithmetic when converting from center and palindrome length back to start and end indices. The formulas start = i - (len - 1) / 2 and end = i + len / 2 handle both parities correctly, but the even case is easy to get wrong under pressure. Testing with a known input like "AABB" helps catch these bugs.
Manacher's algorithm achieves O(n) time by transforming the string with separator characters and reusing previously computed palindrome radii through a mirror property. It is worth mentioning in an interview to show awareness of the optimal solution, but it is rarely required to code live because it is intricate and error-prone.
Remember one sentence: try every character and every gap as a palindrome center, expand outward while both sides match, and keep the longest span found.
---