Count all substrings having character K | Function to return the index of the next occurrence of character ch in strr starting from the given index ; Return the index of the first occurrence of ch ; No occurrence found ; Function to return the count of all the substrings of strr which contain the character ch at least one ; To store the count of valid substrings ; Index of the first occurrence of ch in strr ; No occurrence of ch after index i in strr ; Substrings starting at index i and ending at indices j , j + 1 , ... , n - 1 are all valid substring ; Driver code
def nextOccurrence ( strr , n , start , ch ) : NEW_LINE INDENT for i in range ( start , n ) : NEW_LINE INDENT if ( strr [ i ] == ch ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT def countSubStr ( strr , n , ch ) : NEW_LINE INDENT cnt = 0 NEW_LINE j = nextOccurrence ( strr , n , 0 , ch ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT while ( j != - 1 and j < i ) : NEW_LINE INDENT j = nextOccurrence ( strr , n , j + 1 , ch ) NEW_LINE DEDENT if ( j == - 1 ) : NEW_LINE INDENT break NEW_LINE DEDENT cnt += ( n - j ) NEW_LINE DEDENT return cnt NEW_LINE DEDENT strr = " geeksforgeeks " NEW_LINE n = len ( strr ) NEW_LINE ch = ' k ' NEW_LINE print ( countSubStr ( strr , n , ch ) ) NEW_LINE