Count of sub-strings that contain character X at least once
Given a string str and a character X. The task is to find the total number of sub-strings that contain the character X at least once.
Examples:
Input: str = “abcd”, X = ‘b’
Output: 6
“ab”, “abc”, “abcd”, “b”, “bc” and “bcd” are the required sub-strings.
Input: str = “w3wiki”, X = ‘e’
Output: 66
Approach: Total number of sub-strings are n * (n + 1) / 2, among them only those sub-strings need to be counted which contain character X. Character X is present in those sub-strings from position of X to the length of the string. For each character before X this sub-string must be counted.
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 count of // required sub-strings int countSubStr(string str, int n, char x) { int res = 0, count = 0; for ( int i = 0; i < n; i++) { if (str[i] == x) { // Number of sub-strings from position // of current x to the end of str res += ((count + 1) * (n - i)); // To store the number of characters // before x count = 0; } else count++; } return res; } // Driver code int main() { string str = "abcabc" ; int n = str.length(); char x = 'c' ; cout << countSubStr(str, n, x); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the count of // required sub-strings static int countSubStr(String str, int n, char x) { int res = 0 , count = 0 ; for ( int i = 0 ; i < n; i++) { if (str.charAt(i) == x) { // Number of sub-strings from position // of current x to the end of str res += ((count + 1 ) * (n - i)); // To store the number of characters // before x count = 0 ; } else count++; } return res; } // Driver code public static void main(String[] args) { String str = "abcabc" ; int n = str.length(); char x = 'c' ; System.out.println(countSubStr(str, n, x)); } } // This code has been contributed by 29AjayKumar |
Python3
# Python implementation of the approach # Function to return the count of # required sub-strings def countSubStr( str , n, x): res = 0 ; count = 0 ; for i in range (n): if ( str [i] = = x): # Number of sub-strings from position # of current x to the end of str res + = ((count + 1 ) * (n - i)); # To store the number of characters # before x count = 0 ; else : count + = 1 ; return res; # Driver code str = "abcabc" ; n = len ( str ); x = 'c' ; print (countSubStr( str , n, x)); # This code contributed by PrinciRaj1992 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count of // required sub-strings static int countSubStr(String str, int n, char x) { int res = 0, count = 0; for ( int i = 0; i < n; i++) { if (str[i] == x) { // Number of sub-strings from position // of current x to the end of str res += ((count + 1) * (n - i)); // To store the number of characters // before x count = 0; } else count++; } return res; } // Driver code public static void Main(String[] args) { String str = "abcabc" ; int n = str.Length; char x = 'c' ; Console.WriteLine(countSubStr(str, n, x)); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP implementation of the approach // Function to return the count of // required sub-strings function countSubStr( $str , $n , $x ) { $res = 0; $count = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $str [ $i ] == $x ) { // Number of sub-strings from position // of current x to the end of str $res += (( $count + 1) * ( $n - $i )); // To store the number of characters // before x $count = 0; } else $count ++; } return $res ; } // Driver code $str = "abcabc" ; $n = strlen ( $str ); $x = 'c' ; echo countSubStr( $str , $n , $x ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // required sub-strings function countSubStr(str, n, x) { let res = 0, count = 0; for (let i = 0; i < n; i++) { if (str[i] == x) { // Number of sub-strings from position // of current x to the end of str res += ((count + 1) * (n - i)); // To store the number of characters // before x count = 0; } else count++; } return res; } let str = "abcabc" ; let n = str.length; let x = 'c' ; document.write(countSubStr(str, n, x)); // This code is contributed by divyeshrabadiya07. </script> |
15
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1), no extra space required so it is a constant.