Number of sub-strings that contain the given character exactly k times

0 0 8 minutes read

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(n²).

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-strings
int 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 code
int 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 approach
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;
 
        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-strings
 
 
def 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 code
if __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 approach
using 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-strings
function 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 code
var s = "abada";
var c = 'a';
var k = 2;
document.write( countSubString(s, c, k) + "<br>");
 
</script>

Output:

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 zambiatek!