Count Distinct Subsequences - GeeksforGeeks

Count Distinct Subsequences - GeeksforGeeks
Given a string, find count of distinct subsequences of it.

Input  : str = "gfg"
Output : 7
The seven distinct subsequences are "", "g", "f",
"gf", "fg", "gg" and "gfg" 

Input  : str = "ggg"
Output : 4
The four distinct subsequences are "", "g", "gg"
and "ggg" 

The problem of counting distinct subsequences is easy if all characters of input string are distinct. The count is equal to nC0 + nC1 + nC2 + … nCn = 2n.

How to count distinct subsequences when there can be repetition in input string?
A Simple Solution to count distinct subsequences in a string with duplicates is to generate all subsequences. For every subsequence, store it in a hash table if it doesn’t exist already. Time complexity of this solution is exponential and it requires exponential extra space.

An Efficient Solution doesn’t require generation of subsequences.

Let countSub(n) be count of subsequences of 
first n characters in input string. We can
recursively write it as below. 

countSub(n) = 2*Count(n-1) - Repetition

If current character, i.e., str[n-1] of str has
not appeared before, then 
   Repetition = 0

Else:
   Repetition  =  Count(m)
   Here m is index of previous occurrence of
   current character. We basically remove all
   counts ending with previous occurrence of
   current character.

How does this work?
If there are no repetitions, then count becomes double of count for n-1 because we get count(n-1) more subsequences by adding current character at the end of all subsequences possible with n-1 length.
If there repetitions, then we find count of all distinct subsequences ending with previous occurrence. This count can be obtained be recursively calling for index of previous occurrence.

Since above recurrence has overlapping subproblems, we can solve it using Dynamic Programming.

const int MAX_CHAR = 256;

// Returns count of distinct sunsequences of str.

int countSub(string str)

{

    // Create an array to store index

    // of last

    vector<int> last(MAX_CHAR, -1);

    // Length of input string

    int n = str.length();

    // dp[i] is going to store count of distinct

    // subsequences of length i.

    int dp[n+1];

    // Empty substring has only one subsequence

    dp[0] = 1;

    // Traverse through all lengths from 1 to n.

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

    {

        // Number of subsequences with substring

        // str[0..i-1]

        dp[i] = 2*dp[i-1];

        // If current character has appeared

        // before, then remove all subsequences

        // ending with previous occurrence.

        if (last[str[i-1]] != -1)

            dp[i] = dp[i] - dp[last[str[i-1]]];

        // Mark occurrence of current character

        last[str[i-1]] = (i-1);

    }

    return dp[n];

}

Read full article from Count Distinct Subsequences - GeeksforGeeks

Count permutations that produce positive result - GeeksforGeeks

Count permutations that produce positive result - GeeksforGeeks
Given an array of digits of length n > 1, digits lies within range 0 to 9. We perform sequence of below three operations until we are done with all digits

1. Select starting two digits and add ( + )
2. Then next digit is subtracted ( – ) from result of above step.
3. The result of above step is multiplied ( X ) with next digit.

We perform above sequence of operations linearly with remaining digits.
The task is to find how many permutations of given array that produce positive result after above operations.
For Example, consider input number[] = {1, 2, 3, 4, 5}. Let us consider a permutation 21345 to demonstrate sequence of operations.

1. Add first two digits, result = 2+1 = 3
2. Subtract next digit, result=result-3= 3-3 = 0
3. Multiply next digit, result=result*4= 0*4 = 0
4. Add next digit, result = result+5 = 0+5 = 5
5. result = 5 which is positive so increment count by one

int countPositivePermutations(int number[], int n)

{

    // First sort the array so that we get all permutations

    // one by one using next_permutation.

    sort(number, number+n);

 

    // Initialize result (count of permutations with positive

    // result)

    int count = 0;

 

    // Iterate for all permutation possible and do operation

    // sequentially in each permutation

    do

    {

        // Stores result for current permutation. First we

        // have to select first two digits and add them

        int curr_result = number[0] + number[1];

 

        // flag that tells what operation we are going to

        // perform

        // operation = 0 ---> addition operation ( + )

        // operation = 1 ---> subtraction operation ( - )

        // operation = 0 ---> multiplication operation ( X )

        // first sort the array of digits to generate all

        // permutation in sorted manner

        int operation = 1;

 

        // traverse all digits

        for (int i=2; i<n; i++)

        {

            // sequentially perform + , - , X operation

            switch (operation)

            {

            case 0:

                curr_result += number[i];

                break;

            case 1:

                curr_result -= number[i];

                break;

            case 2:

                curr_result *= number[i];

                break;

            }

 

            // next operation (decides case of switch)

            operation = (operation + 1) % 3;

        }

 

        // result is positive then increment count by one

        if (curr_result > 0)

            count++;

 

    // generate next greater permutation until it is

    // possible

    } while(next_permutation(number, number+n));

 

    return count;

}

Read full article from Count permutations that produce positive result - GeeksforGeeks