Longest Palindromic Substring Problem


Description

LeetCode Problem 5.

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: s = "cbbd"
Output: "bb"

Example 3:

1
2
Input: s = "a"
Output: "a"

Example 4:

1
2
Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        int max_len = 0, idx_i = 0, idx_j = 0;
        for (int k = 0; k < n; k ++) {
            for (int i = 0; i < n-k; i ++) {
                int j = i+k;
                if (k == 0) {
                    dp[i][j] = 1;
                } else if (k == 1) {
                    dp[i][j] = (s[i] == s[j]);
                } else {
                    if (dp[i+1][j-1] == 1 && s[i] == s[j])
                        dp[i][j] = 1;
                    else 
                        dp[i][j] = 0;
                }
                
                if (dp[i][j] == 1) {
                    if (j-i+1 > max_len) {
                        max_len = j - i + 1;
                        idx_i = i;
                        idx_j = j;
                    }
                }
            }
        }
        
        return s.substr(idx_i, max_len);
    }
};




Related Posts

Triangle Problem

LeetCode 120. Given a triangle array, return the minimum path...

Pascal's Triangle Problem

LeetCode 118. Given an integer numRows, return the first numRows...

Distinct Subsequences Problem

LeetCode 115. Given two strings s and t, return the...

Best Time To Buy And Sell Stock Problem

LeetCode 121. You are given an array prices where prices[i]...

Best Time To Buy And Sell Stock Iii Problem

LeetCode 123. You are given an array prices where prices[i]...

Best Time To Buy And Sell Stock Ii Problem

LeetCode 122. You are given an integer array prices where...