Longest Palindromic Substring (Length)
Medium About 20 min Free, no account needed
How long is the longest palindrome hiding in the string?
The brief
Given a string s, return the length of its longest palindromic substring.
The obvious approach tests every substring with an inner palindrome check, O(n^3). The hidden test is 5,000 identical characters: every substring is a palindrome, so nothing short-circuits and it's too slow. You will need to do better than O(n^3); O(n2) is ample here.
Starter code
using System;
public class Solution
{
// TODO: return the length of the longest palindromic substring of s.
public int LongestPalindromeLength(string s)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- String processing
- Parse, scan and match text character by character with correct edge cases.
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
Related katas
- Valid Palindrome Easy Free Is the sentence a palindrome once punctuation and case are ignored?
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Decode String Medium Free Expand k[encoded] patterns, nesting included.