Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Expand around every centre (odd and even length) — O(n²).

Example 1

Input

babad

Output

3

Example 2

Input

cbbd

Output

2

Hints

  1. Every palindrome has a centre: one character (odd length) or the gap between two characters (even length).
  2. 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