Problem

Given a string s, return the longest palindromic substring in s.
input: s = "babad"
output: "bab" or "aba"
input: s = "cbbd"
output: "bb"
input: s = "ac"
output: "a"
input: s = "a"
output: "a"

code(cpp)

time complexity: \( O(n^2) \)
for \( \rightarrow n \) times
while \( \rightarrow \frac{n}{2} \) times
\( n\times ((\frac{n}{2}+1)+\frac{n}{2}) = O(n^2)\)

理解

假設字串長度為n個字元，
for已經固定找n次，
如果暴力破解用當前index下的字元去找接下來所有可能， 會執行\( \sum_{i=0}^{n-1}(n-i)=\frac{n(n+1)}{2} \)次，
總執行次數會是 \( n\cdot\frac{n(n+1)}{2} \) ，則時間複雜度會是\( O(n^3) \)。
接下來試試用中間的字元去向外找對稱
因為對稱的字串有奇數跟偶數所以單次for下最多會執行while \( [(\frac{n}{2}+1) + \frac{n}{2}] = (n+1)\)次，
也就是字串本身是對稱的
\( O(1) \)則是在字串裡的字元都沒相同也沒有對稱的情況
for固定會執行n次
取最糟的情況執行while的結果\( (n+1) \)次，
總執行次數為\( n(n+1)\)
因此，時間複雜度會是\( O(n^2) \)。

Reference

Neetcode-youtube

problem link

leetcode