Posts tagged as “Palindrome”

花花酱 LeetCode 1332. Remove Palindromic Subsequences

By zxi on January 26, 2020

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 1000
s only consists of letters ‘a’ and ‘b’

Solution: Math

if s is empty => 0 step
if s is a palindrome => 1 step
Otherwise, 2 steps…
1. delete all the as
2. delete all the bs

Time complexity: O(n)
Space complexity: O(n) / O(1)

C++

// Author: Huahua

class Solution {

public:

int removePalindromeSub(string s) {

if (s.empty()) return 0;

if (s == string(rbegin(s), rend(s))) return 1;

return 2;

}

};

花花酱 LeetCode 1328. Break a Palindrome

By zxi on January 26, 2020

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string. If there is no way to do so, return the empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"

Example 2:

Input: palindrome = "a"
Output: ""

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

Solution: Greedy

For the first half of the string, replace the first non ‘a’ character to ‘a’.

e.g. abcdcba => aacdcba

If not found which means the the entire string is ‘a’ expect the middle one if the length is odd, like aa or aba, replace the last character to ‘b’.

aa => ab
aba => abb

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string breakPalindrome(string palindrome) {

const int n = palindrome.length();

if (n == 1) return "";

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

if (palindrome[i] != 'a') {

palindrome[i] = 'a';

return palindrome;

}

palindrome.back() = 'b';

return palindrome;

}

};

花花酱 LeetCode 1312. Minimum Insertion Steps to Make a String Palindrome

By zxi on January 4, 2020

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

Constraints:

1 <= s.length <= 500
All characters of s are lower case English letters.

Solution: DP

dp[i][j] := min chars to insert
dp[j][j] = dp[i-1][j+1] if s[i] == s[j] else min(dp[i+1][j] , dp[i][j-1]) + 1
base case: dp[i][i] = 0
ans: dp[0][n-1]

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

C++

// Author: Huahua

class Solution {

public:

int minInsertions(string s) {

const int n = s.length();

vector<vector<int>> dp(n, vector<int>(n));

for (int l = 2; l <= n; ++l)

for (int i = 0, j = l - 1; j < n; ++i, ++j)

dp[i][j] = s[i] == s[j] ? dp[i + 1][j - 1] : min(dp[i + 1][j], dp[i][j - 1]) + 1;

return dp[0][n - 1];

}

};

花花酱 LeetCode 132. Palindrome Partitioning II

By zxi on December 7, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution: DP

dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.

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

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// valid[i][j] = 1 if s[i~j] is palindrome, otherwise 0

vector<vector<int>> valid(n, vector<int>(n, 1));

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j)

valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1];

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

if (valid[0][i]) {

dp[i] = 0;

continue;

}

for (int j = 0; j < i; ++j)

if (valid[j + 1][i])

dp[i] = min(dp[i], dp[j] + 1);

}

return dp[n - 1];

}

};

DP v2

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

for (int m = 0; m < n; ++m)

for (int d = 0; d <= 1; ++d)

for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j)

dp[j] = min(dp[j], (i ? (dp[i - 1] + 1) : 0));

return dp[n - 1];

}

};

花花酱 LeetCode 131. Palindrome Partitioning

By zxi on October 10, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution1: DP

dp[i] := ans of str[0:i]
dp[j] = { x + str[i:len] for x in dp[i] }, 0 <= i < len

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

C++

// Author: Huahua

bool isPalindrome(const string& s) {

const int n = s.length();

for (int i = 0; i < n / 2; ++i)

if (s[i] != s[n - 1 - i]) return false;

return true;

}

class Solution {

public:

vector<vector<string>> partition(string s) {

int n = s.length();

vector<vector<vector<string>>> dp(n + 1);

for (int len = 1; len <= n; ++len) {

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

string right = s.substr(i, len - i);

if (!isPalindrome(right)) continue;

if (i == 0) dp[len].push_back({right});

for (const auto& p : dp[i]) {

dp[len].push_back(p);

dp[len].back().push_back(right);

}

return dp[n];

}

};

Solution 2: DFS

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

C++

// Author: Huahua

bool isPalindrome(const string& s, int l, int r) {

while (l < r)

if (s[l++] != s[r--]) return false;

return true;

}

class Solution {

public:

vector<vector<string>> partition(string s) {

int n = s.length();

vector<vector<string>> ans;

vector<string> cur;

function<void(int)> dfs = [&](int start) {

if (start == n) {

ans.push_back(cur);

return;

}

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

if (!isPalindrome(s, start, i)) continue;

cur.push_back(s.substr(start, i - start + 1));

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

Posts tagged as “Palindrome”

花花酱 LeetCode 1332. Remove Palindromic Subsequences

Solution: Math

C++

花花酱 LeetCode 1328. Break a Palindrome

Solution: Greedy

C++

花花酱 LeetCode 1312. Minimum Insertion Steps to Make a String Palindrome

Solution: DP

C++

花花酱 LeetCode 132. Palindrome Partitioning II

Solution: DP

C++

C++

Related Problems

花花酱 LeetCode 131. Palindrome Partitioning

Solution1: DP

C++

Solution 2: DFS

C++