Count substrings that starts with character X and ends with character Y
Given a string str of n lowercase characters, the task is to count the number of substrings of str starting with character X and ending with character Y.
Examples:
Input: str = "abbcaceghcak" x = 'a', y = 'c' Output: 5 abbc, abbcac, ac, abbcaceghc, aceghc Input: str = "w3wiki" x = 'g', y = 'e' Output: 6
Approach:
- Initialize two counters i.e. tot_count to count the total number of substrings and count_x to count the number of strings that start with X.
- Start traversing the string.
- If the current character is X then increment the count of count_x.
- If the current character is Y, it means a string ends at Y so increment the count of tot_count i.e.
tot_count = tot_count + count_x
- It means that if there exists a Y then it will make a substring with all the X occurs before Y in the string. So, add the count of X to the total count.
- Return total count.
Below is the implementation of above approach:
C++
// C++ implementation to count substrings // starting with character X and ending // with character Y #include <bits/stdc++.h> using namespace std; // function to count substrings starting with // character X and ending with character Y int countSubstr(string str, int n, char x, char y) { // to store total count of // required substrings int tot_count = 0; // to store count of character 'x' // up to the point the string 'str' // has been traversed so far int count_x = 0; // traverse 'str' from left to right for ( int i = 0; i < n; i++) { // if true, increment 'count_x' if (str[i] == x) count_x++; // if true accumulate 'count_x' // to 'tot_count' if (str[i] == y) tot_count += count_x; } // required count return tot_count; } // Driver code int main() { string str = "abbcaceghcak" ; int n = str.size(); char x = 'a' , y = 'c' ; cout << "Count = " << countSubstr(str, n, x, y); return 0; } |
Java
// Java implementation to count // substrings starting with // character X and ending // with character Y import java.util.*; import java.lang.*; import java.io.*; class GFG { // function to count substrings // starting with character X and // ending with character Y static int countSubstr(String str, int n, char x, char y) { // to store total count of // required substrings int tot_count = 0 ; // to store count of character // 'x' up to the point the // string 'str' has been // traversed so far int count_x = 0 ; // traverse 'str' from // left to right for ( int i = 0 ; i < n; i++) { // if true, increment 'count_x' if (str.charAt(i) == x) count_x++; // if true accumulate 'count_x' // to 'tot_count' if (str.charAt(i) == y) tot_count += count_x; } // required count return tot_count; } // Driver code public static void main(String args[]) { String str = "abbcaceghcak" ; int n = str.length(); char x = 'a' , y = 'c' ; System.out.print ( "Count = " + countSubstr(str, n, x, y)); } } // This code is contributed // by Subhadeep |
Python3
# Python 3 implementation to count substrings # starting with character X and ending # with character Y # function to count substrings starting with # character X and ending with character Y def countSubstr( str , n, x, y): # to store total count of # required substrings tot_count = 0 # to store count of character 'x' # up to the point the string 'str' # has been traversed so far count_x = 0 # traverse 'str' from left to right for i in range (n): # if true, increment 'count_x' if str [i] = = x: count_x + = 1 # if true accumulate 'count_x' # to 'tot_count' if str [i] = = y: tot_count + = count_x # required count return tot_count # Driver Code str = 'abbcaceghcak' n = len ( str ) x, y = 'a' , 'c' print ( 'Count =' , countSubstr( str , n, x, y)) # This code is contributed SamyuktaSHegde |
C#
// C# implementation to count substrings // starting with character X and ending // with character Y using System; class GFG { // function to count substrings starting // with character X and ending with character Y static int countSubstr( string str, int n, char x, char y) { // to store total count of // required substrings int tot_count = 0; // to store count of character 'x' up // to the point the string 'str' has // been traversed so far int count_x = 0; // traverse 'str' from left to right for ( int i = 0; i < n; i++) { // if true, increment 'count_x' if (str[i] == x) count_x++; // if true accumulate 'count_x' // to 'tot_count' if (str[i] == y) tot_count += count_x; } // required count return tot_count; } // Driver code public static void Main() { string str = "abbcaceghcak" ; int n = str.Length; char x = 'a' , y = 'c' ; Console.Write( "Count = " + countSubstr(str, n, x, y)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation to count substrings // starting with character X and ending // with character Y // function to count substrings starting with // character X and ending with character Y function countSubstr( $str , $n , $x , $y ) { // to store total count of // required substrings $tot_count = 0; // to store count of character 'x' // up to the point the string 'str' // has been traversed so far $count_x = 0; // traverse 'str' from left to right for ( $i = 0; $i < $n ; $i ++) { // if true, increment 'count_x' if ( $str [ $i ] == $x ) $count_x ++; // if true accumulate 'count_x' // to 'tot_count' if ( $str [ $i ] == $y ) $tot_count += $count_x ; } // required count return $tot_count ; } // Driver code $str = "abbcaceghcak" ; $n = strlen ( $str ); $x = 'a' ; $y = 'c' ; echo "Count = " . countSubstr( $str , $n , $x , $y ); // This code is contributed // by Akanksha Rai |
Javascript
<script> // JavaScript implementation to count substrings // starting with character X and ending // with character Y // function to count substrings starting with // character X and ending with character Y function countSubstr(str, n, x, y) { // to store total count of // required substrings var tot_count = 0; // to store count of character 'x' // up to the point the string 'str' // has been traversed so far var count_x = 0; // traverse 'str' from left to right for ( var i = 0; i < n; i++) { // if true, increment 'count_x' if (str[i] === x) count_x++; // if true accumulate 'count_x' // to 'tot_count' if (str[i] === y) tot_count += count_x; } // required count return tot_count; } // Driver code var str = "abbcaceghcak" ; var n = str.length; var x = "a" , y = "c" ; document.write( "Count = " + countSubstr(str, n, x, y)); </script> |
Output
Count = 5
Complexity Analysis:
- Time Complexity: O(n), to iterate over the array where n is the size of the given string
- Auxiliary Space: O(1),as no extra space is required
Contact Us