Count of substrings having all distinct characters | C ++ Program to implement the above appraoach ; Function to count total number of valid substrings ; Stores the count of substrings ; Stores the frequency of characters ; Initialised both pointers to beginning of the string ; If all characters in substring from index i to j are distinct ; Increment count of j - th character ; Add all substring ending at j and starting at any index between i and j to the answer ; Increment 2 nd pointer ; If some characters are repeated or j pointer has reached to end ; Decrement count of j - th character ; Increment first pointer ; Return the final count of substrings ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long int countSub ( string str ) { int n = ( int ) str . size ( ) ; long long int ans = 0 ; int cnt [ 26 ] ; memset ( cnt , 0 , sizeof ( cnt ) ) ; int i = 0 , j = 0 ; while ( i < n ) { if ( j < n && ( cnt [ str [ j ] - ' a ' ] == 0 ) ) { cnt [ str [ j ] - ' a ' ] ++ ; ans += ( j - i + 1 ) ; j ++ ; } else { cnt [ str [ i ] - ' a ' ] -- ; i ++ ; } } return ans ; } int main ( ) { string str = " gffg " ; cout << countSub ( str ) ; return 0 ; }