lis_lcs.cpp

/*
Longest Increasing Subsequence (LIS) & Longest Common Subsequence (LCS)
Mathematical Foundation:
LIS: dp[i] = max length ending at i, Binary search O(n log n)
LCS: dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
Time: LIS O(n log n), LCS O(n*m)
*/

#include <bits/stdc++.h>
using namespace std;

// LIS - O(n log n) with Binary Search
// LeetCode: 300. Longest Increasing Subsequence
// https://leetcode.com/problems/longest-increasing-subsequence/
// Related:
// 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// 646. Maximum Length of Pair Chain
// https://leetcode.com/problems/maximum-length-of-pair-chain/
// 673. Number of Longest Increasing Subsequence
// https://leetcode.com/problems/number-of-longest-increasing-subsequence/
// 1105. Filling Bookcase Shelves
// https://leetcode.com/problems/filling-bookcase-shelves/
// 435. Non-overlapping Intervals
// https://leetcode.com/problems/non-overlapping-intervals/
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

// LIS - Return actual sequence
// LeetCode: 300. Longest Increasing Subsequence (variant)
// https://leetcode.com/problems/longest-increasing-subsequence/
// Related:
// 673. Number of Longest Increasing Subsequence
// https://leetcode.com/problems/number-of-longest-increasing-subsequence/
// 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// 1048. Longest String Chain
// https://leetcode.com/problems/longest-string-chain/
// 368. Largest Divisible Subset
// https://leetcode.com/problems/largest-divisible-subset/
vector<int> findLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1), parent(n, -1);
    int maxLen = 1, maxIdx = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }
    
    vector<int> lis;
    int curr = maxIdx;
    while (curr != -1) {
        lis.push_back(nums[curr]);
        curr = parent[curr];
    }
    reverse(lis.begin(), lis.end());
    return lis;
}

// Longest Decreasing Subsequence
// Related LeetCode Problems:
// 300. Longest Increasing Subsequence (reverse approach)
// https://leetcode.com/problems/longest-increasing-subsequence/
// 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// 646. Maximum Length of Pair Chain
// https://leetcode.com/problems/maximum-length-of-pair-chain/
// 1105. Filling Bookcase Shelves
// https://leetcode.com/problems/filling-bookcase-shelves/
int lengthOfLDS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x, greater<int>());
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

// Russian Doll Envelopes (2D LIS)
// LeetCode: 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// Related:
// 300. Longest Increasing Subsequence
// https://leetcode.com/problems/longest-increasing-subsequence/
// 646. Maximum Length of Pair Chain
// https://leetcode.com/problems/maximum-length-of-pair-chain/
// 435. Non-overlapping Intervals
// https://leetcode.com/problems/non-overlapping-intervals/
// 1048. Longest String Chain
// https://leetcode.com/problems/longest-string-chain/
int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](auto& a, auto& b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });
    
    vector<int> heights;
    for (auto& e : envelopes) heights.push_back(e[1]);
    return lengthOfLIS(heights);
}

// LCS - Standard DP
// LeetCode: 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// Related:
// 72. Edit Distance
// https://leetcode.com/problems/edit-distance/
// 1035. Uncrossed Lines
// https://leetcode.com/problems/uncrossed-lines/
// 718. Maximum Length of Repeated Subarray
// https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// 1092. Shortest Common Supersequence
// https://leetcode.com/problems/shortest-common-supersequence/
// 583. Delete Operation for Two Strings
// https://leetcode.com/problems/delete-operation-for-two-strings/
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

// LCS - Space Optimized
// LeetCode: 1143. Longest Common Subsequence (optimized)
// https://leetcode.com/problems/longest-common-subsequence/
// Related:
// 72. Edit Distance
// https://leetcode.com/problems/edit-distance/
// 97. Interleaving String
// https://leetcode.com/problems/interleaving-string/
// 115. Distinct Subsequences
// https://leetcode.com/problems/distinct-subsequences/
// 712. Minimum ASCII Delete Sum for Two Strings
// https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
int longestCommonSubsequenceOptimized(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    if (m < n) swap(text1, text2), swap(m, n);
    
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) dp[j] = prev + 1;
            else dp[j] = max(dp[j], dp[j - 1]);
            prev = temp;
        }
    }
    return dp[n];
}

// Print LCS (Backtracking)
// LeetCode: 1143. Longest Common Subsequence (variant)
// https://leetcode.com/problems/longest-common-subsequence/
// Related:
// 1092. Shortest Common Supersequence
// https://leetcode.com/problems/shortest-common-supersequence/
// 583. Delete Operation for Two Strings
// https://leetcode.com/problems/delete-operation-for-two-strings/
// 712. Minimum ASCII Delete Sum for Two Strings
// https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
// 1035. Uncrossed Lines
// https://leetcode.com/problems/uncrossed-lines/
string printLCS(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    string lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (text1[i - 1] == text2[j - 1]) {
            lcs = text1[i - 1] + lcs;
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}

// Shortest Common Supersequence
// LeetCode: 1092. Shortest Common Supersequence
// https://leetcode.com/problems/shortest-common-supersequence/
// Related:
// 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// 583. Delete Operation for Two Strings
// https://leetcode.com/problems/delete-operation-for-two-strings/
// 712. Minimum ASCII Delete Sum for Two Strings
// https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
// 72. Edit Distance
// https://leetcode.com/problems/edit-distance/
string shortestCommonSupersequence(string str1, string str2) {
    string lcs = printLCS(str1, str2);
    string result;
    int i = 0, j = 0, k = 0;
    
    while (k < lcs.size()) {
        while (i < str1.size() && str1[i] != lcs[k]) {
            result += str1[i++];
        }
        while (j < str2.size() && str2[j] != lcs[k]) {
            result += str2[j++];
        }
        result += lcs[k++];
        i++; j++;
    }
    
    result += str1.substr(i) + str2.substr(j);
    return result;
}

// Number of LIS
// LeetCode: 673. Number of Longest Increasing Subsequence
// https://leetcode.com/problems/number-of-longest-increasing-subsequence/
// Related:
// 300. Longest Increasing Subsequence
// https://leetcode.com/problems/longest-increasing-subsequence/
// 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// 646. Maximum Length of Pair Chain
// https://leetcode.com/problems/maximum-length-of-pair-chain/
// 1048. Longest String Chain
// https://leetcode.com/problems/longest-string-chain/
// 368. Largest Divisible Subset
// https://leetcode.com/problems/largest-divisible-subset/
int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> len(n, 1), cnt(n, 1);
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                } else if (len[j] + 1 == len[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        maxLen = max(maxLen, len[i]);
    }
    
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (len[i] == maxLen) result += cnt[i];
    }
    return result;
}