Posts tagged as “Palindrome”

花花酱 LeetCode 1616. Split Two Strings to Make Palindrome

By zxi on October 10, 2020

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: a_prefix and a_suffix where a = a_prefix + a_suffix, and splitting b into two strings: b_prefix and b_suffix where b = b_prefix + b_suffix. Check if a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

When you split a string s into s_prefix and s_suffix, either s_suffix or s_prefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

Example 1:

Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
Then, a_prefix + b_suffix = "" + "y" = "y", which is a palindrome.

Example 2:

Input: a = "abdef", b = "fecab"
Output: true

Example 3:

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
Then, a_prefix + b_suffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example 4:

Input: a = "xbdef", b = "xecab"
Output: false

Constraints:

1 <= a.length, b.length <= 10⁵
a.length == b.length
a and b consist of lowercase English letters

Solution: Greedy

Try to match the prefix of A and suffix of B (or the other way) as much as possible and then check whether the remaining part is a palindrome or not.

e.g. A = “abcxyzzz”, B = “uuuvvcba”
A’s prefix abc matches B’s suffix cba
We just need to check whether “xy” or “vv” is palindrome or not.
The concatenated string “abc|vvcba” is a palindrome, left abc is from A and vvcba is from B.

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

C++

// Author: Huahua

class Solution {

public:

bool checkPalindromeFormation(string a, string b) {

auto isPalindrome = [](const string& s, int i, int j) {

while (i < j && s[i] == s[j]) ++i, --j;

return i >= j;

};

auto check = [&isPalindrome](const string& a, const string& b) {

int i = 0;

int j = a.length() - 1;

while (a[i] == b[j]) ++i, --j;

return isPalindrome(a, i, j) || isPalindrome(b, i, j);

};

return check(a, b) || check(b, a);

}

};

花花酱 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];

}

};

Posts tagged as “Palindrome”

花花酱 LeetCode 1616. Split Two Strings to Make Palindrome

Solution: Greedy

C++

花花酱 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