LCS Archives - Huahua's Tech Road

花花酱 LeetCode 1713. Minimum Operations to Make a Subsequence

By zxi on January 3, 2021

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.

Return the minimum number of operations needed to make target a subsequence of arr.

A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4]
Output: 2
Explanation: You can add 5 and 1 in such a way that makes arr = [5,9,4,1,2,3,4], then target will be a subsequence of arr.

Example 2:

Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
Output: 3

Constraints:

1 <= target.length, arr.length <= 10⁵
1 <= target[i], arr[i] <= 10⁹
target contains no duplicates.

Solution: Reduce to LIS

The original problem is a LCS (Longest common subsequence) problem that can be solved in O(n*m) time.
Since the elements in the target array is unique, we can convert the numbers into indices that helps to reduce the problem to LIS (Longest increasing subsequence) that can be solved in O(mlogn) time.

e.g.
target: [6,4,8,1,3,2] => [0, 1, 2, 3, 4, 5]
array: [4,7,6,2,3,8,6,1] => [1,-1, 0, 5, 4, 2, 0, 3] => [1, 0, 5, 4, 2, 3]
and the LIS is [0, 2, 3] => [6, 8, 1], we need to insert the rest of the numbers.
Ans = len(target) – len(LIS)

Time complexity: O(nlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A, vector<int>& B) {

unordered_map<int, int> m;

for (int i = 0; i < A.size(); ++i)

m[A[i]] = i;

vector<int> dp;

for (int x : B) {

auto mit = m.find(x);

if (mit == end(m)) continue;

const int idx = mit->second;

if (dp.empty() || idx > dp.back())

dp.push_back(idx);

else

*lower_bound(begin(dp), end(dp), idx) = idx;

}

return A.size() - dp.size();

}

};

Python3

# Author: Huahua

class Solution:

def minOperations(self, A: List[int], B: List[int]) -> int:

m = {x: i for i, x in enumerate(A)}

dp = []

for x in B:

if x not in m: continue

if not dp or m[x] > dp[-1]: dp.append(m[x])

else: dp[bisect_left(dp, m[x])] = m[x]

return len(A) - len(dp)

花花酱 LeetCode 1143. Longest Common Subsequence

By zxi on August 29, 2019

Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

Solution: DP

Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i] and text2[0:j]
dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])

Time complexity: O(mn)
Space complexity: O(mn) -> O(n)

C++

// Author: Huahua, 16ms 14.9 MB

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int m = text1.length();

int n = text2.length();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

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

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

if (text1[i] == text2[j])

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

else

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

return dp[m][n];

}

};

C++/V2

// Author: Huahua, 8ms, 8.8MB

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int m = text1.length();

int n = text2.length();

vector<int> dp(n + 1);

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

int prev = 0; // dp[i][j]

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

int curr = dp[j + 1]; // dp[i][j + 1]

if (text1[i] == text2[j])

// dp[i + 1][j + 1] = dp[i][j] + 1

dp[j + 1] = prev + 1;

else

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

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

prev = curr;

}

return dp[n]; // dp[m][n]

}

};

C++/V3

// Author: Huahua

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int m = text1.length();

int n = text2.length();

vector<int> dp1(n + 1);

vector<int> dp2(n + 1);

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

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

if (text1[i] == text2[j])

dp2[j + 1] = dp1[j] + 1;

else

dp2[j + 1] = max(dp1[j + 1], dp2[j]);

swap(dp1, dp2);

}

return dp1[n];

}

};

花花酱 LeetCode 1092. Shortest Common Supersequence

By zxi on June 16, 2019

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywherefrom T) results in the string S.)

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a substring of "cabac" because we can delete the first "c".
str2 = "cab" is a substring of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Note:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.

Solution: LCS

Find the LCS (longest common sub-sequence) of two strings, and insert unmatched characters into the LCS.

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua, running time: 16 ms, 15.3 MB

class Solution {

public:

string shortestCommonSupersequence(string str1, string str2) {

int l1 = str1.length();

int l2 = str2.length();

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

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

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

dp[i][j] = str1[i - 1] == str2[j - 1] ?

1 + dp[i - 1][j - 1] :

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

deque<char> ans;

while (l1 || l2) {

char c;

if (l1 == 0) c = str2[--l2];

else if (l2 == 0) c = str1[--l1];

else if (str1[l1 - 1] == str2[l2 - 1]) c = str1[--l1] = str2[--l2];

else if (dp[l1 - 1][l2] == dp[l1][l2]) c = str1[--l1];

else if (dp[l1][l2 - 1] == dp[l1][l2]) c = str2[--l2];

ans.push_front(c);

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest continuous increasing subsequence.

Example 1:

1 2	Input: [1,3,5,4,7] Output: 3

Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.

Example 2:

1 2	Input: [2,2,2,2,2] Output: 1

Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000.

Idea:

Dynamic Programming

Solution:

// Author: Huahua

class Solution {

public:

int findLengthOfLCIS(vector<int>& nums) {

if (nums.empty()) return 0;

int cur = 1;

int ans = 1;

for (int i = 1; i < nums.size(); ++i) {

if (nums[i] > nums[i-1]) {

++cur;

ans = max(ans, cur);

} else {

cur = 1;

}

return ans;

}

};

Posts tagged as “LCS”

花花酱 LeetCode 1713. Minimum Operations to Make a Subsequence

Solution: Reduce to LIS

C++

Python3

花花酱 LeetCode 1143. Longest Common Subsequence

C++

C++/V2

C++/V3

花花酱 LeetCode 1092. Shortest Common Supersequence

Solution: LCS

C++

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence