What is the brute force approach and complexity for Longest Palindromic Substring?

Check every substring from both ends, and remember the longest one that passes with time complexity O(N^3) and space complexity O(1).

What is the optimal approach and complexity for Longest Palindromic Substring?

From each of the 2N − 1 centres, grow outward while the ends match; keep the longest with optimal time complexity O(N^2) and space complexity O(1).

How do you identify the pattern for Longest Palindromic Substring?

Look for key signals in the prompt: "longest palindromic substring" indicates Maximize the length of a palindromic range. The answer is the best over all ranges.; "substring (contiguous)" indicates The answer is one run of letters s[i..j], not letters picked from different places.; "return the substring" indicates Keep the start and the length while searching, then cut the text out of `s` once at the end..

Longest Palindromic Substring

Medium·LeetCode #5 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given a string s. Return the longest part of s that is a palindrome. The part must be a substring, which means one run of letters that sit next to each other in s. A palindrome reads the same forwards and backwards.

If more than one palindrome has the longest length, any one of them is a correct answer.

Input

A string s made of letters and digits.

Output

A substring of s that is a palindrome and has the largest possible length.

Example 1

Input: s = "babad"

Output: "bab"

aba has the same length, so it is also a correct answer.

Example 2

Input: s = "cbbd"

Output: "bb"

bb is the longest palindrome. The two bs sit side by side, so nothing needs to be skipped.

Constraints

• 1 ≤ s.length ≤ 1000
• s consists of only digits and English letters.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“longest palindromic substring”

→ Maximize the length of a palindromic range. The answer is the best over all ranges.

“substring (contiguous)”

→ The answer is one run of letters s[i..j], not letters picked from different places.

“return the substring”

→ Keep the start and the length while searching, then cut the text out of `s` once at the end.

Approach Complexity Ladder

Brute Force — check every substring, keep the longestO(N^3)O(1)

Check every substring from both ends, and remember the longest one that passes

Better — table of palindromes, keep the longestO(N^2)O(N^2)

Build isPal[i][j] by length, and remember the longest cell that is true

Optimal — expand around every centre, keep the bestO(N^2)O(1)

From each of the 2N − 1 centres, grow outward while the ends match; keep the longest

Brute Force Intuition

Try every substring s[i..j]. Check it from both ends, moving inward. If it is a palindrome and longer than the best so far, store its start and length, not the text. At the end, cut the answer out of s once.

Recognition rule for this sub-pattern:

dp[i][j] for the substring s[i..j]; expand from the centre or fill by increasing length.

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture