Count of Substrings that can be formed without using the given list of Characters
Given a string str and a list of characters L, the task is to count the total numbers of substrings of the string str without using characters given in the list L.
Examples:
Input: str = “abcd”, L[] = {‘a’, ‘b’, ‘t’, ‘q’}
Output: 3
Explanation:
On ignoring the characters ‘a’ and ‘b’ from the given string, substring “cd” is left.
Therefore, the total number of substrings formed by “cd” by:
(2 * (2 + 1)) / 2 = 3Input: str = “abcpxyz”, L[] = {‘a’, ‘p’, ‘q’}
Output: 9
Explanation:
On ignoring the characters ‘a’ and ‘p’ from the given string, substrings “bc” and “xyz” are left.
Therefore, the total number of substrings formed by the substrings is:
(2*(2+1))/2 + (3*(3+1))/2 = 3 + 6 = 9
Approach: The total number of substrings for a given string of length N is given by the formula
(N * (N + 1)) / 2
The idea is to use the above formula and follow the below steps to compute the answer:
- Traverse the string str character by character.
- Count the number of characters on which a character from list L is not found. Let the count be N
- Once a character from L is encountered, compute (N * (N + 1) / 2) and add it to the answer and reset the count N to zero.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the Number of sub-strings // without using given character int countSubstring(string& S, char L[], int & n) { int freq[26] = { 0 }, ans = 0; // Mark the given characters in // the freq array for ( int i = 0; i < n; i++) { freq[( int )(L[i] - 'a' )] = 1; } // Count variable to store the count // of the characters until a character // from given L is encountered int count = 0; for ( auto x : S) { // 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 if (freq[( int )(x - 'a' )]) { ans += (count * count + count) / 2; count = 0; } else count++; } // For last remaining characters ans += (count * count + count) / 2; return ans; } // Driver code int main() { string S = "abcpxyz" ; char L[] = { 'a' , 'p' , 'q' }; int n = sizeof (L) / sizeof (L[0]); cout << countSubstring(S, L, n); return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG { // Function to find the Number of sub-Strings // without using given character static int countSubString( char []S, char L[], int n) { int []freq = new int [ 26 ]; int ans = 0 ; // Mark the given characters in // the freq array for ( int i = 0 ; i < n; i++) { freq[( int )(L[i] - 'a' )] = 1 ; } // Count variable to store the count // of the characters until a character // from given L is encountered int count = 0 ; for ( int x : S) { // 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 if (freq[( int )(x - 'a' )] > 0 ) { ans += (count * count + count) / 2 ; count = 0 ; } else count++; } // For last remaining characters ans += (count * count + count) / 2 ; return ans; } // Driver code public static void main(String[] args) { String S = "abcpxyz" ; char L[] = { 'a' , 'p' , 'q' }; int n = L.length; System.out.print(countSubString(S.toCharArray(), L, n)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the above approach # Function to find the Number of sub-strings # without using given character def countSubstring(S, L,n): freq = [ 0 for i in range ( 26 )] # the freq array for i in range (n): freq[( ord (L[i]) - ord ( 'a' ))] = 1 # Count variable to store the count # of the characters until a character # from given L is encountered count,ans = 0 , 0 for x in S: # 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 if (freq[ ord (x) - ord ( 'a' )]): ans + = (count * count + count) / / 2 count = 0 else : count + = 1 # For last remaining characters ans + = (count * count + count) / / 2 return ans # Driver code S = "abcpxyz" L = [ 'a' , 'p' , 'q' ] n = len (L) print (countSubstring(S, L, n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approach using System; class GFG { // Function to find the Number of sub-Strings // without using given character static int countSubString( char []S, char []L, int n) { int []freq = new int [26]; int ans = 0; // Mark the given characters in // the freq array for ( int i = 0; i < n; i++) { freq[( int )(L[i] - 'a' )] = 1; } // Count variable to store the count // of the characters until a character // from given L is encountered int count = 0; foreach ( int x in S) { // 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 if (freq[( int )(x - 'a' )] > 0) { ans += (count * count + count) / 2; count = 0; } else count++; } // For last remaining characters ans += (count * count + count) / 2; return ans; } // Driver code public static void Main() { string S = "abcpxyz" ; char []L = { 'a' , 'p' , 'q' }; int n = L.Length; Console.WriteLine(countSubString(S.ToCharArray(), L, n)); } } // This code is contributed by Yash_R |
Javascript
<script> // JavaScript implementation of the above approach // Function to find the Number of sub-Strings // without using given character function countSubString(S, L, n) { var freq = new Array(26).fill(0); var ans = 0; // Mark the given characters in // the freq array for ( var i = 0; i < n; i++) { freq[L[i].charCodeAt(0) - "a" .charCodeAt(0)] = 1; } // Count variable to store the count // of the characters until a character // from given L is encountered var count = 0; for (const x of S) { // 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 if (freq[x.charCodeAt(0) - "a" .charCodeAt(0)] > 0) { ans = ans + parseInt((count * count + count) / 2); count = 0; } else count++; } // For last remaining characters ans += parseInt((count * count + count) / 2); return ans; } // Driver code var S = "abcpxyz" ; var L = [ "a" , "p" , "q" ]; var n = L.length; document.write(countSubString(S.split( "" ), L, n)); </script> |
9
Time Complexity: O(n + |S|)
Auxiliary Space: O(26)
Contact Us