MEDIUM NC#103 Blind #57 1-D Dynamic Programming / Expand Around Center
5. Longest Palindromic Substring
š Problem
Given a string s, return the length of the longest palindromic substring in s.
š§ Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- ā¢Array methods (`push`, `pop`, `shift`, `slice`)
- ā¢Object/Map/Set usage patterns
- ā¢Function parameter and return typing
- ā¢Array DP table updates
- ā¢State transition thinking
- ā¢Base case initialization
Logical Thinking Concepts
- ā¢Define invariants before coding
- ā¢Check edge cases first (`[]`, single element, duplicates)
- ā¢Estimate time/space before implementation
- ā¢Apply Dynamic Programming reasoning pattern
š” Approach
- ā Expand around each character as center for potential palindrome
- ā Use helper function to check if substring is palindrome
- ā Track max length found
- ā Time: O(nĀ²), Space: O(1)
š ļø Hints & Pitfalls
Hints
- ā¢Expand around each character as center for potential palindrome
- ā¢Use helper function to check if substring is palindrome
- ā¢Track max length found
Common Pitfalls
- ā¢Time: O(nĀ²), Space: O(1)
š§Ŗ Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
longestPalindrome('babad'); Expected:
3 Test Case 2
Not run Input:
longestPalindrome('cbbd'); Expected:
2 Test Case 3
Not run Input:
longestPalindrome('a'); Expected:
1 š Code Editor
š¤ Output