# 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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:str = “abcd”, L[] = {‘a’, ‘b’, ‘t’, ‘q’}Output:3Explanation:

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 = 3

Input:str = “abcpxyz”, L[] = {‘a’, ‘p’, ‘q’}Output:9Explanation:

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>` |

**Output:**

9