Count all substrings having character K | C ++ implementation of the approach ; Function to return the index of the next occurrence of character ch in str 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 str which contain the character ch at least one ; To store the count of valid substrings ; Index of the first occurrence of ch in str ; No occurrence of ch after index i in str ; Substrings starting at index i and ending at indices j , j + 1 , ... , n - 1 are all valid substring ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int nextOccurrence ( string str , int n , int start , char ch ) { for ( int i = start ; i < n ; i ++ ) { if ( str [ i ] == ch ) return i ; } return -1 ; } int countSubStr ( string str , int n , char ch ) { int cnt = 0 ; int j = nextOccurrence ( str , n , 0 , ch ) ; for ( int i = 0 ; i < n ; i ++ ) { while ( j != -1 && j < i ) { j = nextOccurrence ( str , n , j + 1 , ch ) ; } if ( j == -1 ) break ; cnt += ( n - j ) ; } return cnt ; } int main ( ) { string str = " geeksforgeeks " ; int n = str . length ( ) ; char ch = ' k ' ; cout << countSubStr ( str , n , ch ) ; return 0 ; }