Posts tagged as “subsequence”

花花酱 LeetCode 1930. Unique Length-3 Palindromic Subsequences

By zxi on December 30, 2021

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

Constraints:

3 <= s.length <= 10⁵
s consists of only lowercase English letters.

Solution: Enumerate first character of a palindrome

For a length 3 palindrome, we just need to enumerate the first character c.
We found the first and last occurrence of c in original string and scan the middle part to see how many unique characters there.

e.g. aabca
Enumerate from a to z, looking for a*a, b*b, …, z*z.
For a*a, aabca, we found first and last a, in between is abc, which has 3 unique letters.
We can use a hastable or a bitset to track unique letters.

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

C++

// Author: Huahua

class Solution {

public:

int countPalindromicSubsequence(string s) {

auto count = [&](char c) -> int {

int l = s.find_first_of(c);

int r = s.find_last_of(c);

if (l == string::npos || r == string::npos) return 0;

bitset<26> m;

for (int i = l + 1; i < r; ++i)

m.set(s[i] - 'a');

return m.count();

};

int ans = 0;

for (char c = 'a'; c <= 'z'; ++c)

ans += count(c);

return ans;

}

};

花花酱 LeetCode 1898. Maximum Number of Removable Characters

By zxi on August 11, 2021

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Solution: Binary Search + Two Pointers

If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.

For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).

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

C++

// Author: Huahua

class Solution {

public:

int maximumRemovals(string s, string p, vector<int>& removable) {

const int n = s.length();

const int t = p.length();

const int m = removable.size();

int l = 0;

int r = m + 1;

vector<int> idx(n, INT_MAX);

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

idx[removable[i]] = i;

while (l < r) {

int mid = l + (r - l) / 2;

int j = 0;

for (int i = 0; i < n && j < t; ++i)

if (idx[i] >= mid && s[i] == p[j]) ++j;

if (j != t)

r = mid;

else

l = mid + 1;

}

// l is the smallest number s.t. p is no longer a subseq of s.

return l - 1;

}

};

花花酱 LeetCode 1771. Maximize Palindrome Length From Subsequences

By zxi on February 21, 2021

You are given two strings, word1 and word2. You want to construct a string in the following manner:

Choose some non-empty subsequence subsequence1 from word1.
Choose some non-empty subsequence subsequence2 from word2.
Concatenate the subsequences: subsequence1 + subsequence2, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.

A palindrome is a string that reads the same forward as well as backward.

Example 1:

Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Example 2:

Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.

Example 3:

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.

Constraints:

1 <= word1.length, word2.length <= 1000
word1 and word2 consist of lowercase English letters.

Solution: DP

Let s = word1 + word2, build dp table on s. We just need to make sure there’s at least one char from each string.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

string s = word1 + word2;

const int n = l1 + l2;

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

for (int i = 0; i < n; ++i) dp[i][i] = 1;

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

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

if (s[i] == s[j])

dp[i][j] = dp[i + 1][j - 1] + 2;

else

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

}

int ans = 0;

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

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

if (word1[i] == word2[j])

ans = max(ans, dp[i][l1 + j]);

return ans;

}

};

O(m+n) Space complexity

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(string word1, string word2) {

const int l1 = word1.length();

const int l2 = word2.length();

string s = word1 + word2;

const int n = l1 + l2;

vector<int> dp1(n, 1), dp2(n);

int ans = 0;

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

vector<int> dp(n);

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

if (s[i] == s[j]) {

dp[i] = dp2[i + 1] + 2;

if (i < l1 && j >= l1)

ans = max(ans, dp[i]);

} else {

dp[i] = max(dp1[i + 1], dp1[i]);

}

// dp2, dp1 = dp1, dp

dp1.swap(dp);

dp2.swap(dp);

}

return ans;

}

};

花花酱 LeetCode 1458. Max Dot Product of Two Subsequences

By zxi on May 24, 2020

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:

1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

Solution: DP

dp[i][j] := max product of nums1[0~i], nums2[0~j].

dp[i][j] = max(dp[i-1][j], dp[i][j -1], max(0, dp[i-1][j-1]) + nums1[i]*nums2[j])

Time complexity: O(n1*n2)
Space complexity: O(n1*n2)

C++

// Author: Huahua

class Solution {

public:

int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// dp[i][j] = max dot product of two subsequences

// of nums1[0:i] and nums2[0:j]

vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN / 2));

for (int i = 1; i <= n1; ++i)

for (int j = 1; j <= n2; ++j)

dp[i][j] = max({

dp[i - 1][j],

dp[i][j - 1],

max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1]

});

return dp[n1][n2];

}

};

C++

// Author: Huahua

class Solution {

public:

int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// dp[i][j] = max dot product of two subsequences

// of nums1[0~i] and nums2[0~j]

vector<vector<int>> dp(n1, vector<int>(n2));

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

for (int j = 0; j < n2; ++j) {

dp[i][j] = nums1[i] * nums2[j];

if (i > 0 && j > 0) dp[i][j] += max(0, dp[i - 1][j - 1]);

if (i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j]);

if (j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1]);

}

return dp.back().back();

}

};

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

}

};