Two dynamic-programming-like problems this week, the amount of lines of code is not a lot, but the ideas behind them are interesting.

32. Longest Valid Parenthesis

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

My accepted code can be found here

Solving this problem is not hard, we know that when we continuously matching valid parenthesis, we can keep track of the current length of valid parenthesis, in the mean time, we keep track of the length of the longest one.

The idea is rather simple, but the implementation is a little bit tricky. When we are reducing a pair of parenthesis on the top of the stack, we need to look at 1. The pair of valid parenthesis inside the current pair. And the length of valid parenthesis immediately before it.

And my algorithm is as below, since all items in the stack is the left parenthesis, so the stack only stores the position index of them.

LongestValidParenthesis(s: string): int:
    let dp = int[length(s)]
    let stack = empty stack of int
    fill dp with 0
    for i = 1 to s.size():
        if s[i] == '(' then stack.push(i)
        else if stack.empty then continue
        else
            let t = stack.pop
            if t == 0 then dp[i] = 2 + dp[i - 1]
            else dp[i] = 2 + dp[i - 1] + dp[t - 1]
    return max(dp)

inside the loop dp[i - 1] is the length of parenthesis inside current pair, and dp[t - 1] is the length of parenthesis before before the current pair. Since the dp value on the position of left parenthesis is always 0, so we don’t need to check whether the left of current pair is the end of another matched pair.

The time and space complexity are both O(n), although space complexity could be optimize to O(1), since all we want to know is the length inside and immediately before the current match.

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Here is an example: S = "rabbbit", T = "rabbit"

Return 3.

My accepted code can be found here

This dp is extremely tricky I think. Although the dp equation is extremely simple. Here it is:

DistinctSubsequences(S: string, T: string):
    let dp = int[length(S)][length(T) + 1]
    dp[0][0] = 1
    for all i, j in range:
        dp[i][j] = dp[i - 1][j]
        if S[i] == T[j - 1] then dp[i][j] += dp[i - 1][j - 1]

where the cell of dp[i][j] is the number of distinct subsequences in S[0 to i] of T[0 to j - 1]. The base case of the dp is: the distinct subsequences in the string of a single character of an empty string is 1. And induction case are, the number of subsequences of S[0 to i] inherits the number of that in S[0 to i - 1]. If the S[i] and T[j - 1] is equal, then S[0 to i] additionally inherits the result of number of subsequences in S[0 to i - 1] of T[0 to j - 2].

The time complexity is O(mn), space complexity can be optimize to O(m) like normal dp problem.