Count of Substrings that can be formed without using the given list of Characters | C ++ implementation of the above approach ; Function to find the Number of sub - strings without using given character ; Mark the given characters in the freq array ; Count variable to store the count of the characters until a character from given L is encountered ; If a character from L is encountered , then the answer variable is incremented by the value obtained by using the mentioned formula and count is set to 0 ; For last remaining characters ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubstring ( string & S , char L [ ] , int & n ) { int freq [ 26 ] = { 0 } , ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { freq [ ( int ) ( L [ i ] - ' a ' ) ] = 1 ; } int count = 0 ; for ( auto x : S ) { if ( freq [ ( int ) ( x - ' a ' ) ] ) { ans += ( count * count + count ) / 2 ; count = 0 ; } else count ++ ; } ans += ( count * count + count ) / 2 ; return ans ; } int main ( ) { string S = " abcpxyz " ; char L [ ] = { ' a ' , ' p ' , ' q ' } ; int n = sizeof ( L ) / sizeof ( L [ 0 ] ) ; cout << countSubstring ( S , L , n ) ; return 0 ; }