Count of substrings which contains a given character K times | Function to count the number of substrings which contains the character C exactly K times ; left and right counters for characters on both sides of subwindow ; left and right pointer on both sides of subwindow ; Initialize the frequency ; result and Length of string ; initialize the left pointer ; initialize the right pointer ; traverse all the window substrings ; counting the characters on leftSide of subwindow ; counting the characters on rightSide of subwindow ; Add the possible substrings on both sides to result ; Setting the frequency for next subwindow ; reset the left , right counters ; Driver code
def countSubString ( s , c , k ) : NEW_LINE INDENT leftCount = 0 NEW_LINE rightCount = 0 NEW_LINE left = 0 NEW_LINE right = 0 NEW_LINE freq = 0 NEW_LINE result = 0 NEW_LINE Len = len ( s ) NEW_LINE while ( s [ left ] != c and left < Len ) : NEW_LINE INDENT left += 1 NEW_LINE leftCount += 1 NEW_LINE DEDENT right = left + 1 NEW_LINE while ( freq != ( k - 1 ) and ( right - 1 ) < Len ) : NEW_LINE INDENT if ( s [ right ] == c ) : NEW_LINE INDENT freq += 1 NEW_LINE DEDENT right += 1 NEW_LINE DEDENT while ( left < Len and ( right - 1 ) < Len ) : NEW_LINE INDENT while ( s [ left ] != c and left < Len ) : NEW_LINE INDENT left += 1 NEW_LINE leftCount += 1 NEW_LINE DEDENT while ( right < Len and s [ right ] != c ) : NEW_LINE INDENT if ( s [ right ] == c ) : NEW_LINE INDENT freq += 1 NEW_LINE DEDENT right += 1 NEW_LINE rightCount += 1 NEW_LINE DEDENT result = ( result + ( leftCount + 1 ) * ( rightCount + 1 ) ) NEW_LINE freq = k - 1 NEW_LINE leftCount = 0 NEW_LINE rightCount = 0 NEW_LINE left += 1 NEW_LINE right += 1 NEW_LINE DEDENT return result NEW_LINE DEDENT s = "3123231" NEW_LINE c = '3' NEW_LINE k = 2 NEW_LINE print ( countSubString ( s , c , k ) ) NEW_LINE