Definition
- Expand-around-center technique – every palindrome has a center, and we try all possible centers to find the longest palindromic substring.
- Odd-length centers – each of the n characters is a potential center for an odd-length palindrome.
- Even-length centers – each of the n-1 gaps between adjacent characters is a potential center for an even-length palindrome.
- Expansion rule – from each center, expand two pointers outward while the characters at both ends match and stay in bounds.
- Complexity – O(n^2) time in the worst case, O(1) extra space.
A reference-code checker at the National Bank of India looks for the longest mirror-symmetric stretch inside a code. Rajesh stands at each possible middle point and grows outward in both directions as long as the two sides keep matching, remembering the widest mirror he finds.
Understanding the Concepts
What is the Longest Palindromic Substring problem?
The problem asks you to find the longest contiguous substring within a given string that reads the same forwards and backwards. For example, in "RACECAR" the entire string is a palindrome, but in "ABACABAD" the longest palindromic substring is "ABACABA" with length 7.
package com.bank.core;
// Input: "NBIBANK"
// Palindromic substrings: "N", "B", "I", "B", "A", "N", "K", "BIB"
// Longest: "BIB" with length 3
Why use expand-around-center?
The brute-force approach checks every possible substring and tests whether it is a palindrome, giving O(n^3) time. A DP approach can reduce this to O(n^2) time and O(n^2) space. Expand-around-center achieves O(n^2) time with O(1) space by observing that every palindrome has a center, and expanding from the center is the natural way to find palindromes.
package com.bank.core;
// Brute force: O(n^3) - check all substrings
// DP approach: O(n^2) time, O(n^2) space
// Expand-around-center: O(n^2) time, O(1) space <- best for interviews
// Manacher: O(n) time, O(n) space <- advanced
How does the expansion work?
For each center, you start two pointers at the center and expand outward. The left pointer moves left and the right pointer moves right as long as both are in bounds and the characters match. When the loop exits, it has overshot by one step on each side, so the actual palindrome runs from left + 1 to right - 1.
package com.bank.service;
public class LongestPalindromeSubstring {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0;
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
// Odd-length palindrome centered at i
int len1 = expand(s, i, i);
// Even-length palindrome centered between i and i+1
int len2 = expand(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expand(String s, int left, int right) {
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// Length of palindrome: right - left - 1
return right - left - 1;
}
public static void main(String[] args) {
LongestPalindromeSubstring solver = new LongestPalindromeSubstring();
System.out.println(solver.longestPalindrome("NBIBANKING"));
System.out.println(solver.longestPalindrome("RACECAR"));
System.out.println(solver.longestPalindrome("ABCBA"));
}
}
BIB
RACECAR
ABCBA
Why are there 2n - 1 centers?
An odd-length palindrome like "ABA" has its center at the character B. An even-length palindrome like "ABBA" has its center in the gap between the two B characters. A string of length n has n single-character centers and n - 1 gap centers, for a total of 2n - 1 centers. Trying all of them guarantees that both odd-length and even-length palindromes are found.
package com.bank.core;
// String "ABBA" (length 4)
// Single-char centers: A(0), B(1), B(2), A(3) -> 4 centers
// Gap centers: A|B(0-1), B|B(1-2), B|A(2-3) -> 3 centers
// Total: 4 + 3 = 7 = 2*4 - 1
// The palindrome "ABBA" is found by expanding from gap center (1,2)
Why does the expansion return right - left - 1?
The while loop increments right and decrements left as long as the characters match. When the loop exits, left and right point to the first positions where the characters do not match (or are out of bounds). The actual palindrome therefore spans from left + 1 to right - 1, and its length is (right - 1) - (left + 1) + 1 = right - left - 1.
package com.bank.core;
// Example: s = "ABCBA", center = index 2 ('C')
// Expansion:
// left=2, right=2: 'C'=='C' -> left=1, right=3
// left=1, right=3: 'B'=='B' -> left=0, right=4
// left=0, right=4: 'A'=='A' -> left=-1, right=5
// left=-1: out of bounds, loop exits
// Palindrome: s[0..4] = "ABCBA", length = 5 - (-1) - 1 = 5
How does this compare to the DP approach?
The DP approach fills a boolean table where dp[i][j] is true if the substring from index i to j is a palindrome. It uses O(n^2) space for the table. Expand-around-center achieves the same O(n^2) time with O(1) extra space, making it the preferred approach.
| Approach | Time | Space | Best for |
|---|---|---|---|
| Brute force | O(n^3) | O(1) | Never |
| DP table | O(n^2) | O(n^2) | When you need all palindrome info |
| Expand-around-center | O(n^2) | O(1) | Interview standard |
| Manacher | O(n) | O(n) | Competitive programming |
package com.bank.core;
// DP approach (for reference, not recommended in interview):
// boolean[][] dp = new boolean[n][n];
// All single chars are palindromes: dp[i][i] = true
// Check pairs: dp[i][i+1] = (s[i] == s[i+1])
// Fill for length 3+: dp[i][j] = dp[i+1][j-1] && s[i]==s[j]
What about a banking use case?
At the National Bank of India, a reference code validator checks for embedded palindromic checksums in legacy codes. Rajesh needs to find the longest palindromic segment within each code.
package com.bank.service;
public class ChecksumExtractor {
private final LongestPalindromeSubstring solver =
new LongestPalindromeSubstring();
public String extractChecksum(String referenceCode) {
String palindrome = solver.longestPalindrome(referenceCode);
System.out.println("Code: " + referenceCode
+ " -> Palindromic checksum: " + palindrome);
return palindrome;
}
public static void main(String[] args) {
ChecksumExtractor extractor = new ChecksumExtractor();
extractor.extractChecksum("NBI12321X");
extractor.extractChecksum("HDFC4554ABC");
extractor.extractChecksum("ICICI9Z");
}
}
Code: NBI12321X -> Palindromic checksum: 12321
Code: HDFC4554ABC -> Palindromic checksum: 4554
Code: ICICI9Z -> Palindromic checksum: ICICI
What are common mistakes?
The most common mistake is not handling even-length palindromes. If you only expand from single-character centers you miss palindromes like "ABBA". Another mistake is computing the start index incorrectly from the length and center position.
package com.bank.core;
// WRONG: only checking odd-length centers
for (int i = 0; i < s.length(); i++) {
int len = expand(s, i, i); // misses "ABBA" type palindromes
}
// CORRECT: check both odd and even centers
for (int i = 0; i < s.length(); i++) {
int len1 = expand(s, i, i); // odd-length
int len2 = expand(s, i, i + 1); // even-length
int len = Math.max(len1, len2);
}
What should a senior engineer know?
A senior engineer should mention Manacher's algorithm, which solves this in O(n) time by exploiting the mirror property of palindromes. When expanding from a center that falls within a previously found longer palindrome, Manacher reuses the mirror center's expansion to skip redundant comparisons. However, expand-around-center is the expected interview answer because it is simpler, uses constant space, and the O(n^2) time is acceptable for typical input sizes.
package com.bank.core;
// Manacher's insight: if center i is within a larger palindrome
// centered at c with right boundary r, then i's mirror i' = 2*c - i
// gives a lower bound on i's palindrome length.
// This avoids redundant expansion and achieves O(n) total.
// But in interviews, expand-around-center is cleaner and sufficient.
Visual Overview
Expand-around-center for s = "ABCBA":
Centers to try (2*5 - 1 = 9 centers):
Odd centers (single char):
i=0: A -> expand: A (length 1)
i=1: B -> expand: B (length 1)
i=2: C -> expand: C->BCB->ABCBA (length 5)
i=3: B -> expand: B (length 1)
i=4: A -> expand: A (length 1)
Even centers (gap):
i=0,1: A|B -> no match (length 0)
i=1,2: B|C -> no match (length 0)
i=2,3: C|B -> no match (length 0)
i=3,4: B|A -> no match (length 0)
Best: center i=2, length 5 -> "ABCBA"
Expansion detail at center i=2:
┌──────────────────────────────────────┐
│ A B C B A │
│ ^ │
│ center=2 │
│ │
│ Step 1: left=2, right=2 │
│ C == C -> expand │
│ │
│ Step 2: left=1, right=3 │
│ B == B -> expand │
│ │
│ Step 3: left=0, right=4 │
│ A == A -> expand │
│ │
│ Step 4: left=-1, right=5 │
│ Out of bounds -> STOP │
│ Palindrome: s[0..4] = "ABCBA" │
└──────────────────────────────────────┘
Key Takeaway
Longest Palindromic Substring is best solved with the expand-around-center technique for interviews. The key insight is that every palindrome has a center, which is either a single character for odd-length palindromes or the gap between two characters for even-length palindromes. A string of length n has 2n - 1 possible centers, and trying all of them guarantees that both types are found.
For each center, you expand two pointers outward as long as they stay in bounds and the characters on both sides match. When the expansion stops (because characters differ or bounds are hit), the loop has overshot by one on each side, so the actual palindrome runs from left + 1 to right - 1 with length right - left - 1. You track the longest span found across all centers and extract it at the end.
The time complexity is O(n^2) because each of the 2n - 1 centers can expand up to O(n) in the worst case, and the space complexity is O(1) because no extra data structure is needed. This combination of quadratic time and constant space makes it the preferred interview approach over the DP table, which uses O(n^2) space for the same time. Manacher's algorithm achieves O(n) time by reusing mirror information, but its complexity is rarely expected in interviews.
At the National Bank of India, Rajesh used this to extract palindromic checksum segments embedded in legacy reference codes. The expand-around-center approach found the longest symmetric stretch in each code without allocating any additional data structures, making it efficient for batch processing millions of codes.
Remember one sentence: try every center in the string, expand outward while both sides match, and keep the longest palindrome found.
---