Subsequence Problem

Problem domain

Ask for a valid longest subsequence.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

• In general, time complexity would be $O(n^2)$ with DP; if using backtracking, it would be at least $O(2^n)$ because we have to enumerate all subsequences.

• One-dimensional DP

  • memo[i] stores the answer of orginal question with the input reduces to the subarray arr[...i] of original input array arr.
  • E.g., Q300.

• Two-dimensional DP

  • Two strings or arrays input: memo[i][j] stores the answer of orginal question with the inputs reduce to the subarrays arr1[...i] and arr2[...j].
  • E.g., Q72, Q115, Q1143.
  • One string or array input: memo[i][j] stores the answer of orginal question with the input reduces to the subarray arr[i..j].
  • E.g., Q516, Q1312.

---

Edit Distance

• Stanford lecture

class Solution {
    public int minDistance(String word1, String word2) {
        // the edit distance of the substring of word1 end at i and the substring of word2 end at j
        Integer[][] memo = new Integer[word1.length()][word2.length()];

        return dp(word1.length() - 1, word2.length() - 1, word1, word2, memo);
    }

    private int dp(int i, int j, String word1, String word2, Integer[][] memo) {
        if (i == -1) {
            return j + 1;
        }
        if (j == -1) {
            return i + 1;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int distance = Integer.MAX_VALUE;
        if (word1.charAt(i) == word2.charAt(j)) {
            distance = dp(i - 1, j - 1, word1, word2, memo);
        }
        else {
            // insert
            distance = Math.min(distance,
                    dp(i, j - 1, word1, word2, memo) + 1);
            // delete
            distance = Math.min(distance,
                    dp(i - 1, j, word1, word2, memo) + 1);
            // replace
            distance = Math.min(distance,
                    dp(i - 1, j - 1, word1, word2, memo) + 1);
        }
        memo[i][j] = distance;

        return distance;
    }
}

Distinct Subsequences

class Solution {
    public int numDistinct(String s, String t) {
        // the number of distinct subsequences of substring of s end at i which equals the substring of t end at j
        Integer[][] memo = new Integer[s.length()][t.length()];

        return dp(s.length() - 1, t.length() - 1, s, t, memo);
    }

    private int dp(int i, int j, String s, String t, Integer[][] memo) {
        if (j == -1) {
            return 1;
        }
        if (j > i) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int result = 0;
        if (s.charAt(i) == t.charAt(j)) {
            result = dp(i - 1, j - 1, s, t, memo) + dp(i - 1, j, s, t, memo);
        }
        else {
            result = dp(i - 1, j, s, t, memo);
        }
        memo[i][j] = result;

        return result;
    }
}

Longest Increasing Subsequence

  // O(n^2)
  // DP
class Solution {
    public int lengthOfLIS(int[] nums) {
        int max = 1;
        int[] LISEndAt = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int longestBefore = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    longestBefore = Math.max(LISEndAt[j], longestBefore);
                }
            }
            LISEndAt[i] = longestBefore + 1;
            max = Math.max(LISEndAt[i], max);
        }

        return max;
    }
}

• Princeton lecture

// O(NlogN)
// Spider Card game, binary search
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> l = new ArrayList<>();
        for (int n : nums) {
            int insert = Collections.binarySearch(l, n);
            if (insert < 0) {
                insert = -1 * insert - 1;
                if (insert == l.size())
                    l.add(n);
                else
                    l.set(insert, n);
            }
        }
        return l.size();
    }
}

Russian Doll Envelopes

• Variation of Q300.

/**
 * 354. Russian Doll Envelopes
 *
 * Optimal strategy:
 * - Sort by width asc; for equal widths, height desc.
 * - Then find LIS length on heights (strictly increasing) via patience sorting (O(n log n)).
 */
class Solution {

    // Standard optimal implementation
    public int maxEnvelopesUltra(int[][] envelopes) {
        int n = envelopes.length;
        if (n == 0) return 0;

        // Sort: width asc, height desc (to prevent chaining equal widths)
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return b[1] - a[1]; // height desc when widths equal
        });

        // Extract heights
        int[] tails = new int[n];
        int len = 0;

        for (int[] e : envelopes) {
            int h = e[1];

            // lower_bound on tails[0..len): first index with tails[idx] >= h
            int idx = Arrays.binarySearch(tails, 0, len, h);
            if (idx < 0) idx = -idx - 1; // insertion point

            tails[idx] = h;
            if (idx == len) len++;
        }
        return len;
    }

    /**
     * Near-100% optimized variant:
     * - Uses primitive long key sorting (dual-pivot quicksort on long[] is faster than Comparator on object arrays).
     * - Encodes sort key as: key = ((long)w << 32) | (Integer.MAX_VALUE - h).
     *   This sorts by w asc; for equal w, by (MAX-h) asc i.e., h desc.
     */
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if (n == 0) return 0;

        long[] keys = new long[n];
        for (int i = 0; i < n; i++) {
            int w = envelopes[i][0], h = envelopes[i][1];
            keys[i] = (((long) w) << 32) | (Integer.MAX_VALUE - h);
        }
        Arrays.sort(keys);

        int[] tails = new int[n];
        int len = 0;

        for (long key : keys) {
            // Recover height: h = Integer.MAX_VALUE - low32bits
            int h = Integer.MAX_VALUE - (int) (key & 0xffffffffL);

            int idx = Arrays.binarySearch(tails, 0, len, h);
            if (idx < 0) idx = -idx - 1;
            tails[idx] = h;
            if (idx == len) len++;
        }
        return len;
    }

    // O(n^2) DP fallback (simple, for small n)
    // dp[i] = longest chain ending at i (after sorting by width asc, height desc)
    public int maxEnvelopesDP(int[][] envelopes) {
        int n = envelopes.length;
        if (n == 0) return 0;

        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return b[1] - a[1];
        });

        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ?  b[1] - a[1] : a[0] - b[0]);
        // 对高度数组寻找 LIS
        int[] height = new int[n];
        for (int i = 0; i < n; i++)
            height[i] = envelopes[i][1];

        return lengthOfLIS(height);
    }

    // 返回 nums 中 LIS 的长度
    public int lengthOfLIS(int[] nums) {
        int piles = 0, n = nums.length;
        int[] top = new int[n];
        for (int i = 0; i < n; i++) {
            // 要处理的扑克牌
            int poker = nums[i];
            int left = 0, right = piles;
            // 二分查找插入位置
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] >= poker)
                    right = mid;
                else
                    left = mid + 1;
            }
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }
}

Longest Palindromic Subsequence

• class Solution {
      public int longestPalindromeSubseq(String s) {
          Integer[][] memo = new Integer[s.length()][s.length()];
  
          return dp(s, 0, s.length() - 1, memo);
      }
  
      private int dp(String s, int i, int j, Integer[][] memo) {
          if (memo[i][j] != null)
              return memo[i][j];
  
          if (i == j) {
              memo[i][j] = 1;
              return 1;
          }
  
          if (j < i)
              return 0;
  
          int len = 0;
          if (s.charAt(i) == s.charAt(j))
              len = 2 + dp(s, i + 1, j - 1, memo);
          else
              len = Math.max(dp(s, i + 1, j, memo), dp(s, i, j - 1, memo));
          memo[i][j] = len;
  
          return memo[i][j];
      }
  }

Delete Operation for Two Strings

• class Solution {
      public int minDistance(String word1, String word2) {
          Integer[][] memo = new Integer[word1.length() + 1][word2.length() + 1];
  
          return dp(word1, 0, word2, 0, memo);
      }
  
      private int dp(String s1, int i, String s2, int j, Integer[][] memo) {
          if (memo[i][j] != null)
              return memo[i][j];
  
          if (i == s1.length()) {
              memo[i][j] = s2.length() - j;
              return memo[i][j];
          }
  
          if (j == s2.length()) {
              memo[i][j] = s1.length() - i;
              return memo[i][j];
          }
  
          int step = 0;
          if (s1.charAt(i) == s2.charAt(j))
              step = dp(s1, i + 1, s2, j + 1, memo);
          else
              step = Math.min(dp(s1, i + 1, s2, j, memo),
                              dp(s1, i, s2, j + 1, memo)) + 1;
          memo[i][j] = step;
  
          return memo[i][j];
      }
  }

Minimum ASCII Delete Sum for Two Strings

• class Solution {
      public int minimumDeleteSum(String word1, String word2) {
          Integer[][] memo = new Integer[word1.length() + 1][word2.length() + 1];
  
          return dp(word1, 0, word2, 0, memo);
      }
  
      private int dp(String s1, int i, String s2, int j, Integer[][] memo) {
          if (memo[i][j] != null)
              return memo[i][j];
  
          if (i == s1.length() && j == s2.length()) {
              memo[i][j] = 0;
              return 0;
          }
  
          if (i == s1.length()) {
              memo[i][j] = (int) s2.charAt(j) + dp(s1, i, s2, j + 1, memo);
              return memo[i][j];
          }
  
          if (j == s2.length()) {
              memo[i][j] = (int) s1.charAt(i) + dp(s1, i + 1, s2, j, memo);
              return memo[i][j];
          }
  
          int sum = 0;
          if (s1.charAt(i) == s2.charAt(j))
              sum = dp(s1, i + 1, s2, j + 1, memo);
          else
              sum = Math.min(dp(s1, i + 1, s2, j, memo) + (int) s1.charAt(i),
                              dp(s1, i, s2, j + 1, memo) + (int) s2.charAt(j));
          memo[i][j] = sum;
  
          return memo[i][j];
      }
  }

Longest Common Subsequence

• class Solution {
      public int longestCommonSubsequence(String text1, String text2) {
          Integer[][] memo = new Integer[text1.length() + 1][text2.length() + 1];
  
          return dp(text1, 0, text2, 0, memo);
      }
  
      private int dp(String s1, int i, String s2, int j, Integer[][] memo) {
          if (memo[i][j] != null)
              return memo[i][j];
  
          if (i == s1.length() || j == s2.length()) {
              memo[i][j] = 0;
              return 0;
          }
  
          int len = 0;
          if (s1.charAt(i) == s2.charAt(j))
              len = 1 + dp(s1, i + 1, s2, j + 1, memo);
          else
              len = Math.max(dp(s1, i + 1, s2, j, memo),
                              dp(s1, i, s2, j + 1, memo));
          memo[i][j] = len;
  
          return memo[i][j];
      }
  }

Minimum Insertion Steps to Make a String Palindrome

• class Solution {
      public int minInsertions(String s) {
          Integer[][] memo = new Integer[s.length()][s.length()];
  
          return dp(s, 0, s.length() - 1, memo);
      }
  
      private int dp(String s, int i, int j, Integer[][] memo) {
          if (memo[i][j] != null)
              return memo[i][j];
  
          if (i == j) {
              memo[i][j] = 0;
              return 0;
          }
  
          if (i > j)
              return 0;
  
          int insertion = 0;
          if (s.charAt(i) == s.charAt(j))
              insertion = dp(s, i + 1, j - 1, memo);
          else
              insertion = Math.min(dp(s, i + 1, j, memo), dp(s, i, j - 1, memo)) + 1;
          memo[i][j] = insertion;
  
          return memo[i][j];
      }
  }