Count of sub-strings that do not consist of the given character
Given a string str and a character c. The task is to find the number of sub-strings that do not consist of the character c.
Examples:
Input: str = “baa”, c = ‘b’
Output: 3
The sub-strings are “a”, “a” and “aa”Input: str = “ababaa”, C = ‘b’
Output: 5
Approach: Initially take a counter that counts the number of characters continuously with no character c. Iterate in the string and increase the counter till str[i] != c. Once str[i] == c, the number of sub-strings from the contiguous length cnt will be (cnt * (cnt + 1)) / 2. After the complete traversal of the string also add (cnt *(cnt + 1)) / 2 to the result for the group of characters appearing after the last occurrence of c.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the number // of sub-strings that do not contain // the given character c int countSubstrings(string s, char c) { // Length of the string int n = s.length(); int cnt = 0; int sum = 0; // Traverse in the string for ( int i = 0; i < n; i++) { // If current character is different // from the given character if (s[i] != c) cnt++; else { // Update the number of sub-strings sum += (cnt * (cnt + 1)) / 2; // Reset count to 0 cnt = 0; } } // For the characters appearing // after the last occurrence of c sum += (cnt * (cnt + 1)) / 2; return sum; } // Driver code int main() { string s = "baa" ; char c = 'b' ; cout << countSubstrings(s, c); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the number // of sub-strings that do not contain // the given character c static int countSubstrings(String s, char c) { // Length of the string int n = s.length(); int cnt = 0 ; int sum = 0 ; // Traverse in the string for ( int i = 0 ; i < n; i++) { // If current character is different // from the given character if (s.charAt(i) != c) cnt++; else { // Update the number of sub-strings sum += (cnt * (cnt + 1 )) / 2 ; // Reset count to 0 cnt = 0 ; } } // For the characters appearing // after the last occurrence of c sum += (cnt * (cnt + 1 )) / 2 ; return sum; } // Driver code public static void main(String[] args) { String s = "baa" ; char c = 'b' ; System.out.println(countSubstrings(s, c)); } } // This code is contributed by Code_Mech. |
Python3
# Python3 implementation of the approach # Function to return the number # of sub-strings that do not contain # the given character c def countSubstrings(s, c): # Length of the string n = len (s) cnt = 0 Sum = 0 # Traverse in the string for i in range (n): # If current character is different # from the given character if (s[i] ! = c): cnt + = 1 else : # Update the number of sub-strings Sum + = (cnt * (cnt + 1 )) / / 2 # Reset count to 0 cnt = 0 # For the characters appearing # after the last occurrence of c Sum + = (cnt * (cnt + 1 )) / / 2 return Sum # Driver code s = "baa" c = 'b' print (countSubstrings(s, c)) # This code is contributed # by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the number // of sub-strings that do not contain // the given character c static int countSubstrings( string s, char c) { // Length of the string int n = s.Length; int cnt = 0; int sum = 0; // Traverse in the string for ( int i = 0; i < n; i++) { // If current character is different // from the given character if (s[i] != c) cnt++; else { // Update the number of sub-strings sum += (cnt * (cnt + 1)) / 2; // Reset count to 0 cnt = 0; } } // For the characters appearing // after the last occurrence of c sum += (cnt * (cnt + 1)) / 2; return sum; } // Driver code public static void Main() { string s = "baa" ; char c = 'b' ; Console.Write(countSubstrings(s, c)); } } // This code is contributed by Akanksha Rai |
PHP
<?php // PHP implementation of the approach // Function to return the number // of sub-strings that do not contain // the given character c function countSubstrings( $s , $c ) { // Length of the string $n = strlen ( $s ); $cnt = 0; $sum = 0; // Traverse in the string for ( $i = 0; $i < $n ; $i ++) { // If current character is different // from the given character if ( $s [ $i ] != $c ) $cnt ++; else { // Update the number of sub-strings $sum += floor (( $cnt * ( $cnt + 1)) / 2); // Reset count to 0 $cnt = 0; } } // For the characters appearing // after the last occurrence of c $sum += floor (( $cnt * ( $cnt + 1)) / 2); return $sum ; } // Driver code $s = "baa" ; $c = 'b' ; echo countSubstrings( $s , $c ); // This code is contributed by Ryuga ?> |
Javascript
<script> // javascript implementation of the approach // Function to return the number // of sub-strings that do not contain // the given character c function countSubstrings( s, c) { // Length of the string var n = s.length; var cnt = 0; var sum = 0; // Traverse in the string for (i = 0; i < n; i++) { // If current character is different // from the given character if (s.charAt(i) != c) cnt++; else { // Update the number of sub-strings sum += (cnt * (cnt + 1)) / 2; // Reset count to 0 cnt = 0; } } // For the characters appearing // after the last occurrence of c sum += (cnt * (cnt + 1)) / 2; return sum; } // Driver code var s = "baa" ; var c = 'b' ; document.write(countSubstrings(s, c)); // This code contributed by umadevi9616 </script> |
3
Time Complexity: O(n) where n is the length of the string
Auxiliary Space: O(1)
New Approach:- Here an alternative approach to count the number of substrings that do not contain a given character in a string
- Initialize a counter variable to 0.
- Initialize two pointers, start and end, to 0.
- Find the length of the string and store it in the variable n.
- Traverse the string using the end pointer until it reaches the end of the string.
- If the current character is equal to the given character, calculate the number of substrings that do not contain the given character using the formula (end – start) * (end – start + 1) / 2, and add it to the counter variable.
- Reset the start pointer to the next character after the current character.
- Increment the end pointer.
- Calculate the number of substrings that do not contain the given character for the remaining characters in the string, and add it to the counter variable.
- Return the final count.
- In the main function, initialize the input string and character, call the countSubstrings function, store the returned value in a variable, and print it.
Here’s the implementation of the above approach in Java:
C++
#include <iostream> #include <string> using namespace std; // This function takes a string s and a character c, and // counts the number of substrings of s that contain c. int countSubstrings(string s, char c) { int count = 0; // The number of substrings that contain c int start = 0; // The start index of the current substring int end = 0; // The end index of the current substring int n = s.length(); // The length of the string s // Loop through the string s while (end < n) { // If we find the character c, then we have a new // substring that contains c. if (s[end] == c) { // We add the number of substrings that end at // the previous index (end-1), plus the new // substring that ends at the current index // (end). count += (end - start) * (end - start + 1) / 2; // We update the start index to be the next // index after the current index (end+1). start = end + 1; } // We move the end index to the next character in // the string. end++; } // At the end of the loop, we need to add the remaining // substrings that end at the last index (n-1). count += (end - start) * (end - start + 1) / 2; // Return the final count of substrings that contain c. return count; } int main() { string s = "baa" ; // The input string char c = 'b' ; // The character to look for in substrings int count = countSubstrings( s, c); // Count the substrings that contain c cout << count << endl; // Print the final count return 0; } // This code is contributed by sarojmcy2e |
Java
public class Solution { public static void main(String[] args) { String s = "baa" ; char c = 'b' ; int count = countSubstrings(s, c); System.out.println(count); } public static int countSubstrings(String s, char c) { int count = 0 ; int start = 0 ; int end = 0 ; int n = s.length(); while (end < n) { if (s.charAt(end) == c) { count += (end - start) * (end - start + 1 ) / 2 ; start = end + 1 ; } end++; } count += (end - start) * (end - start + 1 ) / 2 ; return count; } } |
Python3
def countSubstrings(s, c): count = 0 start = 0 end = 0 n = len (s) while end < n: if s[end] = = c: count + = (end - start) * (end - start + 1 ) / / 2 start = end + 1 end + = 1 count + = (end - start) * (end - start + 1 ) / / 2 return count s = "baa" c = 'b' count = countSubstrings(s, c) print (count) |
C#
using System; class Program { // This function takes a string s and a character c, and // counts the number of substrings of s that contain c. static int CountSubstrings( string s, char c) { int count = 0; // The number of substrings that contain c int start = 0; // The start index of the current substring int end = 0; // The end index of the current substring int n = s.Length; // The length of the string s // Loop through the string s while (end < n) { // If we find the character c, then we have a // new substring that contains c. if (s[end] == c) { // We add the number of substrings that end // at the previous index (end-1), plus the // new substring that ends at the current // index (end). count += (end - start) * (end - start + 1) / 2; // We update the start index to be the next // index after the current index (end+1). start = end + 1; } // We move the end index to the next character // in the string. end++; } // At the end of the loop, we need to add the // remaining substrings that end at the last index // (n-1). count += (end - start) * (end - start + 1) / 2; // Return the final count of substrings that contain // c. return count; } static void Main( string [] args) { string s = "baa" ; // The input string char c = 'b' ; // The character to look for in // substrings int count = CountSubstrings( s, c); // Count the substrings that contain c Console.WriteLine(count); // Print the final count } } |
Javascript
function countSubstrings(s, c) { let count = 0; // The number of substrings that contain c let start = 0; // The start index of the current substring let end = 0; // The end index of the current substring const n = s.length; // The length of the string s // Loop through the string s while (end < n) { // If we find the character c, then we have a // new substring that contains c. if (s[end] === c) { // We add the number of substrings that end // at the previous index (end-1), plus the // new substring that ends at the current // index (end). count += ((end - start) * (end - start + 1)) / 2; // We update the start index to be the next // index after the current index (end+1). start = end + 1; } // We move the end index to the next character // in the string. end++; } // At the end of the loop, we need to add the // remaining substrings that end at the last index // (n-1). count += ((end - start) * (end - start + 1)) / 2; // Return the final count of substrings that contain // c. return count; } const s = "baa" ; // The input string const c = "b" ; // The character to look for in substrings const count = countSubstrings(s, c); // Count the substrings that contain c console.log(count); // Print the final count |
3
In this code, added the main method and used it to test the countSubstrings method by passing the input values s and c. The countSubstrings method is the same as the given code, which counts the number of substrings in the string s that do not contain the character c.
Time Complexity: The time complexity of the given code is O(n), where n is the length of the string s. This is because we are traversing the string s only once using the end pointer and performing constant-time operations in the while loop.
Auxiliary Space: The auxiliary space required by the given code is O(1), which is constant space. This is because we are not using any additional data structures or arrays to store the intermediate results, and all the calculations are done using the existing variables.
Contact Us