Given a string str and an array arr[] of K characters, the task is to find the number of substrings of str that contain characters only from the given character array arr[].
Note: The string str and the arr[] contain only lowercase alphabets.
Examples:
Input: S = “abcb”, K = 2, charArray[] = {‘a’, ‘b’}
Output: 4
Explanation:
The substrings are “a”, “ab”, “b”, “b” using the available charactersInput: S = “aabdbbtr”, K = 4, charArray[] = {‘e’, ‘a’, ‘r’, ‘t’}
Output: 6
Explanation:
The substrings “a”, “aa”, “a”, “t”, “tr”, “r” using the available characters.
Naive Approach: The naive approach is generate all possible substrings for the given string str and check if each substring consists of given characters in the array arr[] or not. If Yes then count that substring else check for the next substring.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above naive approach can be optimized as we will delete the count of substrings formed by characters which are not present in the given array arr[]. Below are the steps:
- Store the characters present in the array arr[] in a boolean array of size 26, so that the searching of any character can be done in O(1) time.
- The total number of substrings formed by string of length N is (N*(N+1))/2, initialise count as (N*(N+1))/2.
- Traverse the string from left to right and store the index of the last character that we encountered in the string which is not present in the array arr[] using a variable lastPos
- If while traversing the string we encounter any character that is not present in arr[] then we subtract number of substrings that will contain this character and will have a starting point greater than the value of lastPos. Suppose we are at index i then the number of substrings to be subtracted will be given by
(i - lastPos)*(N - i)
- Update the value of lastPos everytime we encounter a character not available in charArray[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of// substrings that can be formed// using given charactersvoid numberofsubstrings(string str, int k, char charArray[]){ int N = str.length(); // Boolean array for storing // the available characters bool available[26] = { 0 }; // Mark indices of all // available characters as 1 for (int i = 0; i < k; i++) { available[charArray[i] - 'a'] = 1; } // Initialize lastPos as -1 int lastPos = -1; // Initialize ans with the total // no of possible substrings int ans = (N * (N + 1)) / 2; // Traverse the string from // left to right for (int i = 0; i < N; i++) { // If the current character // is not present in B if (available[str[i] - 'a'] == 0) { // Subtract the total possible // substrings ans -= ((i - lastPos) * (N - i)); // Update the value of // lastpos to current index lastPos = i; } } // Print the final answer cout << ans << endl;}// Driver Codeint main(){ // Given String string str = "abcb"; int k = 2; // Given character array char charArray[k] = { 'a', 'b' }; // Function Call numberofsubstrings(str, k, charArray); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;class GFG{ // Function to find the number of// substrings that can be formed// using given characterspublic static void numberofsubstrings(String str, int k, char charArray[]){ int N = str.length(); // Boolean array for storing // the available characters int available[] = new int[26]; Arrays.fill(available, 0); // Mark indices of all // available characters as 1 for(int i = 0; i < k; i++) { available[charArray[i] - 'a'] = 1; } // Initialize lastPos as -1 int lastPos = -1; // Initialize ans with the total // no of possible substrings int ans = (N * (N + 1)) / 2; // Traverse the string from // left to right for(int i = 0; i < N; i++) { // If the current character // is not present in B if (available[str.charAt(i) - 'a'] == 0) { // Subtract the total possible // substrings ans -= ((i - lastPos) * (N - i)); // Update the value of // lastpos to current index lastPos = i; } } // Print the final answer System.out.println(ans);}// Driver Codepublic static void main(String args[]){ // Given String String str = "abcb"; int k = 2; // Given character array char []charArray = {'a', 'b'}; // Function Call numberofsubstrings(str, k, charArray);}}// This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach# Function to find the number of# substrings that can be formed# using given charactersdef numberofsubstrings(str, k, charArray): N = len(str) # Boolean array for storing # the available characters available = [0] * 26 # Mark indices of all # available characters as 1 for i in range(0, k): available[ord(charArray[i]) - ord('a')] = 1 # Initialize lastPos as -1 lastPos = -1 # Initialize ans with the total # no of possible substrings ans = (N * (N + 1)) / 2 # Traverse the string from # left to right for i in range(0, N): # If the current character # is not present in B if (available[ord(str[i]) - ord('a')] == 0): # Subtract the total possible # substrings ans -= ((i - lastPos) * (N - i)) # Update the value of # lastpos to current index lastPos = i # Print the final answer print(int(ans))# Driver Code# Given Stringstr = "abcb"k = 2# Given character arraycharArray = [ 'a', 'b' ]# Function callnumberofsubstrings(str, k, charArray)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the number of// substrings that can be formed// using given characterspublic static void numberofsubstrings(String str, int k, char []charArray){ int N = str.Length; // Boolean array for storing // the available characters int []available = new int[26]; // Mark indices of all // available characters as 1 for(int i = 0; i < k; i++) { available[charArray[i] - 'a'] = 1; } // Initialize lastPos as -1 int lastPos = -1; // Initialize ans with the total // no of possible substrings int ans = (N * (N + 1)) / 2; // Traverse the string from // left to right for(int i = 0; i < N; i++) { // If the current character // is not present in B if (available[str[i] - 'a'] == 0) { // Subtract the total possible // substrings ans -= ((i - lastPos) * (N - i)); // Update the value of // lastpos to current index lastPos = i; } } // Print the final answer Console.WriteLine(ans);}// Driver Codepublic static void Main(String []args){ // Given String String str = "abcb"; int k = 2; // Given character array char []charArray = {'a', 'b'}; // Function Call numberofsubstrings(str, k, charArray);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program for the above approach// Function to find the number of// substrings that can be formed// using given charactersfunction numberofsubstrings(str, k, charArray){ var N = str.length; // Boolean array for storing // the available characters var available = [ 26 ]; // Mark indices of all // available characters as 1 for(var i = 0; i < k; i++) { available[charArray[i] - 'a'] = 1; } // Initialize lastPos as -1 var lastPos = -1; // Initialize ans with the total // no of possible substrings var ans = (N * (N + 1)) / 2; // Traverse the string from // left to right for(var i = 0; i < N; i++) { // If the current character // is not present in B if (available[str.charAt(i) - 'a'] == 0) { // Subtract the total possible // substrings ans -= ((i - lastPos) * (N - i)); // Update the value of // lastpos to current index lastPos = i; } } // Print the final answer document.write(ans);}// Driver Code // Given String var str = "abcb"; var k = 2; // Given character array var charArray = ['a', 'b']; // Function Call numberofsubstrings(str, k, charArray);// This code is contributed by shivanisinghss2110.</script> |
Output:
4
Time Complexity: O(N), N is the length of the string
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
