Given the string str, a character c, and an integer k > 0. The task is to find the number of sub-strings that contain the character c exactly k times.
Examples:
Input: str = “abada”, c = ‘a’, K = 2
Output: 4
All possible sub-strings are “aba”, “abad”, “bada” and “ada”.Input: str = “55555”, c = ‘5’, k = 4
Output: 2
Naive approach: A simple solution is to generate all the sub-strings and check whether the count of a given character is exactly k times.
The time complexity of this approach is O(n2).
Space complexity of this approach is O(1).
Efficient approach: An efficient solution is to use the sliding window technique. Find the sub-string that exactly contains the given character k times, starting with character c. Count the number of characters on either side of the sub-string. Multiply the counts to get the number of possible sub-strings. The time complexity of this approach is O(n).
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-stringsint countSubString(string s, char c, int k){ // Left and right counters for characters on // both sides of sub-string window int leftCount = 0, rightCount = 0; // Left and right pointer on both // sides of sub-string window int left = 0, right = 0; // Initialize the frequency int freq = 0; // Result and length of string int result = 0, len = s.length(); // Initialize the left pointer while (s[left] != c && left < len) { left++; leftCount++; } // Initialize the right pointer right = left + 1; while (freq != (k - 1) && (right - 1) < len) { if (s[right] == c) freq++; right++; } // Traverse all the window sub-strings while (left < len && (right - 1) < len) { // Counting the characters on left side // of the sub-string window while (s[left] != c && left < len) { left++; leftCount++; } // Counting the characters on right side // of the sub-string window while (right < len && s[right] != c) { if (s[right] == c) freq++; right++; rightCount++; } // Add the possible sub-strings // on both sides to result result = result + (leftCount + 1) * (rightCount + 1); // Setting the frequency for next // sub-string window freq = k - 1; // Reset the left and right counters leftCount = 0; rightCount = 0; left++; right++; } return result;}// Driver codeint main(){ string s = "abada"; char c = 'a'; int k = 2; cout << countSubString(s, c, k) << "\n"; return 0;} |
Java
import java.io.*; // Java implementation of the approachclass GFG { // Function to return the count of required sub-strings static int countSubString(char[] s, char c, int k) { // Left and right counters for characters on // both sides of sub-string window int leftCount = 0, rightCount = 0; // Left and right pointer on both // sides of sub-string window int left = 0, right = 0; // Initialize the frequency int freq = 0; // Result and length of string int result = 0, len = s.length; // Initialize the left pointer while (s[left] != c && left < len) { left++; leftCount++; } // Initialize the right pointer right = left + 1; while (freq != (k - 1) && (right - 1) < len) { if (s[right] == c) freq++; right++; } // Traverse all the window sub-strings while (left < len && (right - 1) < len) { // Counting the characters on left side // of the sub-string window while (s[left] != c && left < len) { left++; leftCount++; } // Counting the characters on right side // of the sub-string window while (right < len && s[right] != c) { if (s[right] == c) freq++; right++; rightCount++; } // Add the possible sub-strings // on both sides to result result = result + (leftCount + 1) * (rightCount + 1); // Setting the frequency for next // sub-string window freq = k - 1; // Reset the left and right counters leftCount = 0; rightCount = 0; left++; right++; } return result; } // Driver code public static void main(String[] args) { String s = "abada"; char c = 'a'; int k = 2; System.out.println( countSubString(s.toCharArray(), c, k)); }}// This code has been contributed by 29AjayKumar |
Python3
# Python 3 implementation of the approach# Function to return the count# of required sub-stringsdef countSubString(s, c, k): # Left and right counters for characters # on both sides of sub-string window leftCount = 0 rightCount = 0 # Left and right pointer on both # sides of sub-string window left = 0 right = 0 # Initialize the frequency freq = 0 # Result and length of string result = 0 len1 = len(s) # Initialize the left pointer while (s[left] != c and left < len1): left += 1 leftCount += 1 # Initialize the right pointer right = left + 1 while (freq != (k - 1) and (right - 1) < len1): if (s[right] == c): freq += 1 right += 1 # Traverse all the window sub-strings while (left < len1 and (right - 1) < len1): # Counting the characters on left side # of the sub-string window while (s[left] != c and left < len1): left += 1 leftCount += 1 # Counting the characters on right side # of the sub-string window while (right < len1 and s[right] != c): if (s[right] == c): freq += 1 right += 1 rightCount += 1 # Add the possible sub-strings # on both sides to result result = (result + (leftCount + 1) * (rightCount + 1)) # Setting the frequency for next # sub-string window freq = k - 1 # Reset the left and right counters leftCount = 0 rightCount = 0 left += 1 right += 1 return result# Driver codeif __name__ == '__main__': s = "abada" c = 'a' k = 2 print(countSubString(s, c, k))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the count of required sub-strings static int countSubString(char[] s, char c, int k) { // Left and right counters for characters on // both sides of sub-string window int leftCount = 0, rightCount = 0; // Left and right pointer on both // sides of sub-string window int left = 0, right = 0; // Initialize the frequency int freq = 0; // Result and length of string int result = 0, len = s.Length; // Initialize the left pointer while (s[left] != c && left < len) { left++; leftCount++; } // Initialize the right pointer right = left + 1; while (freq != (k - 1) && (right - 1) < len) { if (s[right] == c) freq++; right++; } // Traverse all the window sub-strings while (left < len && (right - 1) < len) { // Counting the characters on left side // of the sub-string window while (s[left] != c && left < len) { left++; leftCount++; } // Counting the characters on right side // of the sub-string window while (right < len && s[right] != c) { if (s[right] == c) freq++; right++; rightCount++; } // Add the possible sub-strings // on both sides to result result = result + (leftCount + 1) * (rightCount + 1); // Setting the frequency for next // sub-string window freq = k - 1; // Reset the left and right counters leftCount = 0; rightCount = 0; left++; right++; } return result; } // Driver code public static void Main(String[] args) { String s = "abada"; char c = 'a'; int k = 2; Console.WriteLine( countSubString(s.ToCharArray(), c, k)); }}// This code contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the approach // Function to return the count of required sub-strings function countSubString($s, $c, $k) { // Left and right counters for characters on // both sides of sub-string window $leftCount = 0; $rightCount = 0; // Left and right pointer on both // sides of sub-string window $left = 0; $right = 0; // Initialize the frequency $freq = 0; // Result and length of string $result = 0; $len = strlen($s); // Initialize the left pointer while ($s[$left] != $c && $left < $len) { $left++; $leftCount++; } // Initialize the right pointer $right = $left + 1; while ($freq != ($k - 1) && ($right - 1) < $len) { if ($s[$right] == $c) $freq++; $right++; } // Traverse all the window sub-strings while ($left < $len && ($right - 1) < $len) { // Counting the characters on left side // of the sub-string window while ($s[$left] != $c && $left < $len) { $left++; $leftCount++; } // Counting the characters on right side // of the sub-string window while ($right < $len && $s[$right] != $c) { if ($s[$right] == $c) $freq++; $right++; $rightCount++; } // Add the possible sub-strings // on both sides to result $result = $result + ($leftCount + 1) * ($rightCount + 1); // Setting the frequency for next // sub-string window $freq = $k - 1; // Reset the left and right counters $leftCount = 0; $rightCount = 0; $left++; $right++; } return $result; } // Driver code $s = "abada"; $c = 'a'; $k = 2; echo countSubString($s, $c, $k), "\n"; // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of required sub-stringsfunction countSubString(s, c, k){ // Left and right counters for characters on // both sides of sub-string window var leftCount = 0, rightCount = 0; // Left and right pointer on both // sides of sub-string window var left = 0, right = 0; // Initialize the frequency var freq = 0; // Result and length of string var result = 0, len = s.length; // Initialize the left pointer while (s[left] != c && left < len) { left++; leftCount++; } // Initialize the right pointer right = left + 1; while (freq != (k - 1) && (right - 1) < len) { if (s[right] == c) freq++; right++; } // Traverse all the window sub-strings while (left < len && (right - 1) < len) { // Counting the characters on left side // of the sub-string window while (s[left] != c && left < len) { left++; leftCount++; } // Counting the characters on right side // of the sub-string window while (right < len && s[right] != c) { if (s[right] == c) freq++; right++; rightCount++; } // Add the possible sub-strings // on both sides to result result = result + (leftCount + 1) * (rightCount + 1); // Setting the frequency for next // sub-string window freq = k - 1; // Reset the left and right counters leftCount = 0; rightCount = 0; left++; right++; } return result;}// Driver codevar s = "abada";var c = 'a';var k = 2;document.write( countSubString(s, c, k) + "<br>");</script> |
Output:
4
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!