Count substrings with same first and last characters | assuming lower case only ; Calculating frequency of each character in the string . ; Computing result using counts ; Driver code
MAX_CHAR = 26 ; NEW_LINE def countSubstringWithEqualEnds ( s ) : NEW_LINE INDENT result = 0 ; NEW_LINE n = len ( s ) ; NEW_LINE count = [ 0 ] * MAX_CHAR ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT count [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 ; NEW_LINE DEDENT for i in range ( MAX_CHAR ) : NEW_LINE INDENT result += ( count [ i ] * ( count [ i ] + 1 ) / 2 ) ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT s = " abcab " ; NEW_LINE print ( countSubstringWithEqualEnds ( s ) ) ; NEW_LINE