Count Distinct Subsequences | Java 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
import java . io . * ; import java . util . * ; class SubsequenceCount { public static int countSub ( String s ) { HashMap < Character , Integer > map = new HashMap < Character , Integer > ( ) ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { map . put ( s . charAt ( i ) , - 1 ) ; } int allCount = 0 ; int levelCount = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { char c = s . charAt ( i ) ; if ( i == 0 ) { allCount = 1 ; map . put ( c , 1 ) ; levelCount = 1 ; continue ; } levelCount = allCount + 1 ; if ( map . get ( c ) < 0 ) { allCount = allCount + levelCount ; } else { allCount = allCount + levelCount - map . get ( c ) ; } map . put ( c , levelCount ) ; } return allCount ; } public static void main ( String [ ] args ) { List < String > list = Arrays . asList ( " abab " , " gfg " ) ; for ( String s : list ) { int cnt = countSub ( s ) ; int withEmptyString = cnt + 1 ; System . out . println ( " With ▁ empty ▁ string ▁ count ▁ for ▁ " + s + " ▁ is ▁ " + withEmptyString ) ; System . out . println ( " Without ▁ empty ▁ string ▁ count ▁ for ▁ " + s + " ▁ is ▁ " + cnt ) ; } } }