5. Longest Substring Without Repeating Characters

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: String、Dynamic Programming

一、題目

Given a string s, return the longest palindromic substring in s.
A string is called a palindrome string if the reverse of that string is the same of the original string.

Example 1:

  • Input: s = “babad”
  • Output: “bab”
  • Explanation: “aba” is also a valid answer.

Example 2:

  • Input: s = “cbbd”
  • Output: “bb”

Constraints:

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

二、分析

  • 注意 palindrome string 的特性：
    • 當長度為 1 時，必為 palindrome string
    • 當長度為 2 時，兩個字元必須相同才為 palindrome string
    • 當長度 >2 時，palindrome string 必須滿足
      1. 最左邊的字元等於最右邊的字元，即 s[left] == s[right]
      2. 除去最左邊的字元跟最右邊的字元，必須為 palindrome string，
        即 s.substr(left+1, len-2) 為 palindromic。

三、解題

1. Dynamic Prograimming

  • Time complexity: \(O(n^2)\)
  • Space complexity: \(O(n^2)\)
string longestPalindrome(string s) {
    int n = s.length();
    string res;
    bool dp[n][n];
    memset(dp, false, sizeof(dp));
    int len = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (i == j) {   // 長度為 1
                dp[i][j] = true;
            } else if (j - i == 1) {    // 長度為 2
                dp[i][j] = s[i] == s[j];
            } else {        // 長度 > 2
                dp[i][j] = s[i] == s[j] && dp[i+1][j-1];
            }

            if (dp[i][j] && j - i + 1 > len) {    // 比較長度
                len = j - i + 1;
                res = s.substr(i, len);
            }
        }
    }
    return res;
}

回目錄 Catalog