Practice › Strings
Longest Palindromic Substring
Medium · Strings · Asked at Amazon, Microsoft, Google, Adobe
Print the length of the longest substring of s that is a palindrome.
Input
One string s (lowercase letters).
Output
The length of the longest palindromic substring.
Constraints
- 1 ≤ |s| ≤ 1000
Expand around every centre (odd and even length) — O(n²).
Example 1
Input
babad
Output
3
Example 2
Input
cbbd
Output
2
Hints
- Every palindrome has a centre: one character (odd length) or the gap between two characters (even length).
- From each of the 2n − 1 centres, expand outwards while the characters on both sides match.
Approach
For each centre, grow l and r outwards while s[l] == s[r]. The palindrome found there has length r − l − 1 once the loop stops. Try both the odd centre (l = r = i) and the even centre (l = i, r = i + 1). There are 2n − 1 centres and each expansion is O(n), so this is O(n²), about 10^6 steps for n = 1000. Manacher's algorithm does it in O(n) but is rarely expected in interviews.
Complexity: O(n²) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int expand(const string &s, int l, int r) {
while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
return r - l - 1;
}
int main() {
string s;
cin >> s;
int best = 0;
for (int i = 0; i < (int)s.size(); i++)
best = max(best, max(expand(s, i, i), expand(s, i, i + 1)));
cout << best << "\n";
return 0;
}Python solution
def expand(s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1
s = input().strip()
print(max(max(expand(s, i, i), expand(s, i, i + 1)) for i in range(len(s))))Java solution
import java.util.*;
public class Main {
static int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return r - l - 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int best = 0;
for (int i = 0; i < s.length(); i++)
best = Math.max(best, Math.max(expand(s, i, i), expand(s, i, i + 1)));
System.out.println(best);
}
}Solve Longest Palindromic Substring online · All practice problems