Leetcode discuss: 940. Distinct Subsequences II

 Here is the link. 

Nov. 4, 2020
940. Distinct Subsequences II

Here are steps I took in order for me to learn a hard DP problem.

1. Read GeeksforGeeks;
2. Copy C# code, ran into failed test caes;
3. Learn another C# submission;
4. Work on a test case

Given a string S, count the number of distinct, non-empty subsequences of S.
Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Define C#: var dp = new int[4]; // s = "abc"
dp[3] = length <=3 distinct subsequences
dp[2] = lenght <=2 distinct subsequences

To remove duplicate, use visited two dimension array.
var visited = new int[length + 1][26]
Go over step by step "abc", how to get the result of 7?
Index = 0;
'a' visited[0,0] -> set true
dp [1, 1, 0, 0] 'a'

"a" - distinct subsequence should be one. "a"

Index = 2
start = 0 'b'
visited[0, 1] -> set true
dp [1, 1, 1, 0]
start = 1
visited[1, 1] -> set true
dp [1, 1, 2, 0]

"ab" - distinct subsequence should be three. "a","b","ab"
Thinking, ask to myself?
Q1: dp[2] = 2, explain to myself, what is meaning of 2.
A1: Append 'b' to all subsequence's in the end, "" + "b" = "b", and "a" + "b"= "ab", two more subsequences are added. Make sense?
Q2: What are total subsequence's number?
A2: dp[1] + dp[2] = 3.

Index = 3
start = 0 'c'
visited [0, 2] -> set true
dp [1, 1, 2, 1] <- start = 0
visited[1, 2] -> set true
[1, 1, 2, 2]-> start = 1
visited[2, 2] -> set true
[1, 1, 2, 4] -> start = 2

The idea is simple. First go over all subsequence with 'c', add them together, each one will append 'c' at the end. In the same time, update dp[index] to include 'c' as well. Two tasks should be completed.

"abc" - distinct subsequence should be 7. "a","b","ab", four are added in the last step - index = 3, itself, "c", add "c" after one of each string {"a","b","ab"}.

The total of "abc" distinct subsequence should be 7.

Advice
As a hard working programmer, it is important for me to go over the test case "abc", each step I like to make sure that code will work for those intermediate result.

The order of any subsequence has to be maintained as the original string. The only challenge is to remove duplicated ones.

Time to work on
It took me more than a few hours to study and write down some notes.Patience is the important. Work on a small test case and try to argue to myself what is true here.

It is hard to be an expert on dynamic programming algorithm. Right now, I just like to learn one hard level algorithm. It took me two days, over 8 hours.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _940_distinct_subsequence_II
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = DistinctSubseqII("abc");
        }

        /// study code
        /// https://www.geeksforgeeks.org/count-distinct-subsequences/
        /// I could not make it work, so I studied another one
        /// https://leetcode.com/problems/distinct-subsequences-ii/discuss/560060/Simple-C-DP-Solution
        public static int DistinctSubseqII(string s)
        {
            long MOD    = 1000 * 1000 * 1000 + 7; 
            long result = 0;
            var  length = s.Length;

            var dp      = new long[length + 1];
            var visited = new bool[length + 1, 26];

            dp[0] = 1;

            for (int index = 1; index <= s.Length; index++)
            {
                var endIndex = s[index - 1] - 'a';
                    
                for (int start = 0; start < index; start++)
                {
                    if (!visited[start, endIndex])
                    {
                        visited[start, endIndex] = true;

                        dp[index] += dp[start];
                        result  += dp[start];

                        dp[index] %= MOD;
                        result  %= MOD;
                    }
                }
            }
               
            return (int)result;
        }
    }
}

Actionable Items

Make a youtube video to explain the algorithm.