Count Distinct Subsequences | C ++ program for above approach ; Returns count of distinct subsequences of str . ; Iterate from 0 to s . length ( ) ; Iterate from 0 to s . length ( ) ; Check if i equal to 0 ; Replace levelCount withe allCount + 1 ; If map is less than 0 ; Return answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSub ( string s ) { map < char , int > Map ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { Map [ s [ i ] ] = -1 ; } int allCount = 0 ; int levelCount = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { char c = s [ i ] ; if ( i == 0 ) { allCount = 1 ; Map = 1 ; levelCount = 1 ; continue ; } levelCount = allCount + 1 ; if ( Map < 0 ) { allCount = allCount + levelCount ; } else { allCount = allCount + levelCount - Map ; } Map = levelCount ; } return allCount ; } int main ( ) { string list [ ] = { " abab " , " gfg " } ; for ( string s : list ) { int cnt = countSub ( s ) ; int withEmptyString = cnt + 1 ; cout << " With ▁ empty ▁ string ▁ count ▁ for ▁ " << s << " ▁ is ▁ " << withEmptyString << endl ; cout << " Without ▁ empty ▁ string ▁ count ▁ for ▁ " << s << " ▁ is ▁ " << cnt << endl ; } return 0 ; }