5. Longest Palindromic Substring
Tags:
Medium
Skills:
StringDP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu tìm Longest Palindromic Substring
Approach - Expand around center
Duyệt từng ký tự làm tâm palindrome (cả tâm lẻ và chẵn), mở sang hai bên để kiểm tra palindrome
Time and space complexity
Solution - Expand around center
1function longestPalindrome(s: string): string {
2 if (s.length <= 1) return s;
3
4 let longest = "";
5
6 function expandAroundCenter(left: number, right: number): string {
7 while (left >= 0 && right < s.length && s[left] === s[right]) {
8 left--;
9 right++;
10 }
11 return s.slice(left + 1, right);
12 }
13
14 for (let i = 0; i < s.length; i++) {
15 const odd_palin = expandAroundCenter(i, i);
16 const even_palin = expandAroundCenter(i, i + 1);
17 if (odd_palin.length > longest.length) {
18 longest = odd_palin;
19 }
20 if (even_palin.length > longest.length) {
21 longest = even_palin
22 }
23 }
24
25 return longest
26}Khi bạn dùng s.slice(left + 1, right) trong hàm expandAroundCenter, lý do là:
while sẽ tiếp tục giảm left-- và tăng right++ miễn là hai ký tự ở vị trí đó giống nhauleft đã nhỏ hơn vị trí bắt đầu của palindrome thực sự, và right đã lớn hơn vị trí kết thúc của palindrome thực sựleft + 1 , chỉ số kết thúc là right - 1Cú pháp slice(begin, end) trong JavaScript/TypeScript sẽ lấy chuỗi từ vị trí begin đến trước vị trí end (không bao gồm end)