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
using System ; using System . Collections . Generic ; class GFG { public static int countSub ( String s ) { Dictionary < char , int > map = new Dictionary < char , int > ( ) ; for ( int i = 0 ; i < s . Length ; i ++ ) { if ( ! map . ContainsKey ( s [ i ] ) ) { map . Add ( 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 ; if ( ! map . ContainsKey ( c ) ) { map . Add ( c , 1 ) ; } else { map = 1 ; } levelCount = 1 ; continue ; } levelCount = allCount + 1 ; if ( map . ContainsKey ( c ) ) { if ( map < 0 ) { allCount = ( allCount + levelCount ) ; } else { allCount = ( allCount + levelCount - map ) ; } } if ( ! map . ContainsKey ( c ) ) { map . Add ( c , levelCount ) ; } else { map = levelCount ; } } return allCount ; } static void Main ( ) { List < string > list = new List < string > ( ) ; list . Add ( " abab " ) ; list . Add ( " gfg " ) ; foreach ( string s in list ) { int cnt = countSub ( s ) ; int withEmptyString = cnt + 1 ; Console . WriteLine ( " With ▁ empty ▁ string ▁ count ▁ for ▁ " + s + " ▁ is ▁ " + withEmptyString ) ; Console . WriteLine ( " Without ▁ empty ▁ string ▁ count ▁ for ▁ " + s + " ▁ is ▁ " + cnt ) ; } } }