Count substrings with same first and last characters | Most efficient C ++ program to count all substrings with same first and last characters . ; assuming lower case only ; Calculating frequency of each character in the string . ; Computing result using counts ; Driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX_CHAR = 26 ; int countSubstringWithEqualEnds ( string s ) { int result = 0 ; int n = s . length ( ) ; int count [ MAX_CHAR ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) count [ s [ i ] - ' a ' ] ++ ; for ( int i = 0 ; i < MAX_CHAR ; i ++ ) result += ( count [ i ] * ( count [ i ] + 1 ) / 2 ) ; return result ; } int main ( ) { string s ( " abcab " ) ; cout << countSubstringWithEqualEnds ( s ) ; return 0 ; }