Count of Distinct Substrings occurring consecutively in a given String | Function to count the distinct substrings placed consecutively in the given string ; Length of the string ; If length of the string does not exceed 1 ; Initialize a DP - table ; Stores the distinct substring ; Iterate from end of the string ; Iterate backward until dp table is all computed ; If character at i - th index is same as character at j - th index ; Update dp [ i ] [ j ] based on previously computed value ; Otherwise ; Condition for consecutively placed similar substring ; Return the count ; Driver Code
def distinctSimilarSubstrings ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE if ( n <= 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT dp = [ [ 0 for x in range ( n + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE substrings = set ( ) NEW_LINE for j in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT for i in range ( j - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( str [ i ] == str [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i + 1 ] [ j + 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] >= j - i ) : NEW_LINE INDENT substrings . add ( str [ i : j - i ] ) NEW_LINE DEDENT DEDENT DEDENT return len ( substrings ) NEW_LINE DEDENT str = " geeksgeeksforgeeks " NEW_LINE print ( distinctSimilarSubstrings ( str ) ) NEW_LINE