Subarray/Substring vs Subsequence and Programs to Generate them

1. visit:  https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/

2. Print all subsequences of a string in Python:

# Python Implementation of the approach import itertools    def Sub_Sequences(STR):     combs = []     for l in range(1, len(STR)+1):         combs.append(list(itertools.combinations(STR, l)))     for c in combs:         for t in c:             print (''.join(t), end =' ')    # Testing with driver code if __name__ == '__main__':     Sub_Sequences('abc')

Output:

a b c ab ac bc abc

3. Count of ‘GFG’ Subsequences in the given string

Examples:

Input : str[] = "GFGFG"
Output : 4
GFGFG, GFGFG, GFGFG, GFGFG

Input : str[] = "ABCFGFPG"
Output : 1

# Python 3 Program to find the "GFG"  # subsequence in the given string MAX = 100    # Print the count of "GFG" subsequence  # in the string def countSubsequence(s, n):     cntG = 0     cntF = 0     result = 0     C=0           # Traversing the given string     for i in range(n):         if (s[i] == 'G'):                            # If the character is 'G', increment             # the count of 'G', increase the result             # and update the array.             cntG += 1             result += C             continue            # If the character is 'F', increment         # the count of 'F' and update the array.         if (s[i] == 'F'):             cntF += 1             C += cntG             continue            # Ignore other character.         else:             continue            print(result)    # Driver Code if __name__ == '__main__':     s = "GFGFG"     n = len(s)     countSubsequence(s, n)        # This code is contributed by # Sanjit_Prasad

Output:

4

Time Complexity : O(n)

4.Count Distinct Subsequences

Given a string, find the count of distinct subsequences of it.

Examples:

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" 

# Python3 program to count number of  # distinct subseqences of a given string    MAX_CHAR = 256    def countSub(ss):        # create an array to store index of last     last = [-1 for i in range(MAX_CHAR + 1)]            # length of input string     n = len(ss)            # dp[i] is going to store count of      # discount subsequence of length of i     dp = [-2 for i in range(n + 1)]             # empty substring has only      # one subseqence     dp[0] = 1            # Traverse through all lengths     # from 1 to n      for i in range(1, n + 1):                    # number of subseqence with          # substring str[0...i-1]         dp[i] = 2 * dp[i - 1]            # if current character has appeared         # before, then remove all subseqences         # ending with previous occurrence.         if last[ord(ss[i - 1])] != -1:             dp[i] = dp[i] - dp[last[ord(ss[i - 1])]]         last[ord(ss[i - 1])] = i - 1            return dp[n]        # Driver code print(countSub("gfg"))    # This code is contributed  # by mohit kumar 29

Output:

7

Time Complexity : O(n)
Auxiliary Space : O(n)

5.Count all subsequences having product less than K

Given a non negative array, find the number of subsequences having product smaller than K.

Examples:

Input : [1, 2, 3, 4] 
        k = 10
Output :11 
The subsequences are {1}, {2}, {3}, {4}, 
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, 
{1, 2, 3}, {1, 2, 4}

Input  : [4, 8, 7, 2] 
         k = 50
Output : 9

# Python3 program to find  
# number of subarrays having  
# product less than k.  
def productSubSeqCount(arr, k): 
    n = len(arr) 
    dp = [[0 for i in range(n + 1)] 
             for j in range(k + 1)] 
    for i in range(1, k + 1): 
        for j in range(1, n + 1): 
              
            # number of subsequence 
            # using j-1 terms  
            dp[i][j] = dp[i][j - 1] 
              
            # if arr[j-1] > i it will  
            # surely make product greater 
            # thus it won't contribute then  
            if arr[j - 1] <= i and arr[j - 1] > 0: 
                  
                # number of subsequence 
                # using 1 to j-1 terms 
                # and j-th term 
                dp[i][j] += dp[i // arr[j - 1]][j - 1] + 1
    return dp[k][n] 
  
# Driver code  
A = [1,2,3,4] 
k = 10
print(productSubSeqCount(A, k)) 
  
# This code is contributed  
# by pk_tautolo 
Output:

11

6. Number of subsequences with positive product
Given an array arr[] of N integers, the task is to find the count of all the subsequences of the array that have positive product.
Example:
Input: arr[] = {2, -3, -1}
Output: 3
{2}, {-3, -1} and {2, -3, -1} are the only possible subsequences.
Input: arr[] = {2, 3, -1, 4, 5}
Output: 15

Efficient approach:
Count the number of positive and negative elements in the array.
Any number of positive elements can be chosen for the subsequence to maintain the positive product. The number of different combinations of subsequences with all the positive elements will be pow(2, count of positive elements).
An even number of negative elements can be chosen for the subsequence to maintain the positive product. The number of different combinations of subsequences with an even number of negative elements will be pow(2, count of negative elements – 1).
After that, remove 1 from the results for the empty subsequence.
Below is the implementation of the above approach:



# Python 3 implementation of the approach  
import math 
  
# Function to return the count of all  
# the subsequences with positive product  
def cntSubSeq(arr, n): 
  
    # To store the count of positive  
    # elements in the array  
    pos_count = 0;  
  
    # To store the count of negative  
    # elements in the array  
    neg_count = 0
  
    for i in range (n): 
  
        # If the current element  
        # is positive  
        if (arr[i] > 0) : 
            pos_count += 1
  
        # If the current element  
        # is negative  
        if (arr[i] < 0):  
            neg_count += 1
  
    # For all the positive  
    # elements of the array  
    result = int(math.pow(2, pos_count))  
  
    # For all the negative  
    # elements of the array  
    if (neg_count > 0): 
        result *= int(math.pow(2, neg_count - 1))  
  
    # For the empty subsequence  
    result -= 1
  
    return result 
  
# Driver code  
arr = [ 2, -3, -1, 4 ]  
n = len (arr);  
  
print (cntSubSeq(arr, n))  
  
# This code is contributed by ANKITKUMAR34 
Output:
7 
Time Complexity: O(n)