Count of substrings formed using a given set of characters only

0 0 6 minutes read

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 characters

Input: 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(N²)
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 characters
void 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 Code
int 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 approach
import java.util.Arrays;
 
class GFG{
     
// Function to find the number of
// substrings that can be formed
// using given characters
public 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 Code
public 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 characters
def 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 String
str = "abcb"
k = 2
 
# Given character array
charArray = [ 'a', 'b' ]
 
# Function call
numberofsubstrings(str, k, charArray)
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the number of
// substrings that can be formed
// using given characters
public 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 Code
public 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 characters
function 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:

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 zambiatek!