Solution: Stack

Use a stack of strings to track all the active strings.
Iterate over the input string:
1. Whenever there is a ‘(‘, push an empty string to the stack.
2. Whenever this is a ‘)’, pop the top string and append the reverse of it to the new stack top.
3. Otherwise, append the letter to the string on top the of stack.

Once done, the (only) string on the top of the stack is the answer.

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string reverseParentheses(string s) {

stack<string> st;

st.push("");

for (char c : s) {

if (c == '(') st.push("");

else if (c != ')') st.top() += c;

else {

string t = st.top(); st.pop();

st.top().insert(end(st.top()), rbegin(t), rend(t));

}

return st.top();

}

};

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution: DP

Try all possible i and find the longest palindromic string whose center is i (odd case) and i / i + 1 (even case).

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms, 8.7 MB

class Solution {

public:

string longestPalindrome(string s) {

const int n = s.length();

auto getLen = [&](int l, int r) {

while (l >= 0 && r < n

&& s[l] == s[r]) {

--l;

++r;

}

return r - l - 1;

};

int len = 0;

int start = 0;

for (int i = 0; i < n; ++i) {

int cur = max(getLen(i, i),

getLen(i, i + 1));

if (cur > len) {

len = cur;

start = i - (len - 1) / 2;

}

return s.substr(start, len);

}

};

Java

// Author: Huahua, 6 ms， 36.5 MB

class Solution {

public String longestPalindrome(String s) {

int len = 0;

int start = 0;

for (int i = 0; i < s.length(); ++i) {

int cur = Math.max(getLen(s, i, i),

getLen(s, i, i + 1));

if (cur > len) {

len = cur;

start = i - (cur - 1) / 2;

}

return s.substring(start, start + len);

}

private int getLen(String s, int l, int r) {

while (l >= 0 && r < s.length()

&& s.charAt(l) == s.charAt(r)) {

--l;

++r;

}

return r - l - 1;

}

Python3

# Author: Huahua, 812 ms, 12.7MB

class Solution:

def longestPalindrome(self, s: str) -> str:

n = len(s)

def getLen(l, r):

while l >= 0 and r < n and s[l] == s[r]:

l -= 1

r += 1

return r - l - 1

start = 0

length = 0

for i in range(n):

cur = max(getLen(i, i),

getLen(i, i + 1))

if cur <= length: continue

length = cur

start = i - (cur - 1) // 2

return s[start : start + length]

Posts tagged as “O(n^2)”

花花酱 LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

Solution: Stack

C++

花花酱 LeetCode 5. Longest Palindromic Substring

Problem

Solution: DP

C++

Java

Python3