Given a string str, the task is to calculate the number of substrings of the given string such that the frequency of each element of the string is almost K.
Examples:
Input: str = “abab”, K = 1
Output: 7
Explanation: The substrings such that the frequency of each character is atmost 1 are “a”, “b”, “a”, “b”, “ab”, “ba” and “ab”.Input: str[] = “xxyyzzxx”, K = 2
Output: 33
Approach: The given problem can be solved using the two-pointer technique. Iterate through each character of the string in the range [0, N) and maintain the frequency of each character in an unordered map. Create a variable ptr, which stores the index of the starting point of the current window. Initially, the value of ptr is 0. For index i, if the frequency of str[i] is less than or equal to K, add (i – ptr + 1) into the substring count, otherwise, increment the value of ptr until str[i] > K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of// substrings such that frequency// of each character is atmost Kint cntSubstr(string str, int K){ // Stores the size of string int N = str.size(); // Stores the final count int ans = 0; // Stores the starting index int ptr = 0; // Stores the frequency of // characters of string unordered_map<char, int> m; // Loop to iterate through string for (int i = 0; i < N; i++) { // Increment the frequency of // the current character m[str[i]]++; // While the frequency of char is // greater than K, increment ptr while (m[str[i]] > K && ptr <= i) { m[str[ptr]]--; ptr++; } // Update count ans += (i - ptr + 1); } // Return Answer return ans;}// Driver Codeint main(){ string str = "abab"; int K = 1; cout << cntSubstr(str, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the count of// substrings such that frequency// of each character is atmost Kstatic int cntSubstr(String str, int K){ // Stores the size of string int N = str.length(); // Stores the final count int ans = 0; // Stores the starting index int ptr = 0; // Stores the frequency of // characters of string HashMap<Character, Integer> m = new HashMap<Character, Integer>(); // Loop to iterate through string for(int i = 0; i < N; i++) { // Increment the frequency of // the current character int count = 0; if (m.containsKey(str.charAt(i))) { count = m.get(str.charAt(i)); } m.put(str.charAt(i), count + 1); // While the frequency of char is // greater than K, increment ptr while (m.get(str.charAt(i)) > K && ptr <= i) { m.put(str.charAt(ptr), m.get(str.charAt(ptr)) - 1); ptr++; } // Update count ans += (i - ptr + 1); } // Return Answer return ans;}// Driver Codepublic static void main(String[] args){ String str = "abab"; int K = 1; System.out.println(cntSubstr(str, K));}}// This code is contributed by ukasp |
Python3
# Python Program to implement# the above approach# Function to find the count of# substrings such that frequency# of each character is atmost Kdef cntSubstr(str, K): # Stores the size of string N = len(str) # Stores the final count ans = 0 # Stores the starting index ptr = 0 # Stores the frequency of # characters of string m = {} # Loop to iterate through string for i in range(N) : # Increment the frequency of # the current character if (str[i] in m): m[str[i]] += 1 else: m[str[i]] = 1 # While the frequency of char is # greater than K, increment ptr while (m[str[i]] > K and ptr <= i): m[str[ptr]] -= 1 ptr += 1 # Update count ans += (i - ptr + 1) # Return Answer return ans# Driver Codestr = "abab"K = 1print(cntSubstr(str, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to find the count of// substrings such that frequency// of each character is atmost Kstatic int cntSubstr(string str, int K){ // Stores the size of string int N = str.Length; // Stores the final count int ans = 0; // Stores the starting index int ptr = 0; // Stores the frequency of // characters of string Dictionary<char, int> m = new Dictionary<char, int>(); // Loop to iterate through string for (int i = 0; i < N; i++) { // Increment the frequency of // the current character int count = 0; if (m.ContainsKey(str[i])) { count = m[str[i]]; } m[str[i]] = count + 1; // While the frequency of char is // greater than K, increment ptr while (m[str[i]] > K && ptr <= i) { m[str[ptr]]--; ptr++; } // Update count ans += (i - ptr + 1); } // Return Answer return ans;}// Driver Codepublic static void Main(){ string str = "abab"; int K = 1; Console.Write(cntSubstr(str, K));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the count of // substrings such that frequency // of each character is atmost K function cntSubstr(str, K) { // Stores the size of string let N = str.length; // Stores the final count let ans = 0; // Stores the starting index let ptr = 0; // Stores the frequency of // characters of string let m = new Map(); // Loop to iterate through string for (let i = 0; i < N; i++) { // Increment the frequency of // the current character if (m.has(str.charAt(i))) m.set(str[i], m.get(str[i]) + 1); else m.set(str[i], 1); // While the frequency of char is // greater than K, increment ptr while (m.get(str[i]) > K && ptr <= i) { m.set(str[ptr], m.get(str[ptr]) - 1); ptr++; } // Update count ans += (i - ptr + 1); } // Return Answer return ans; } // Driver Code let str = "abab"; let K = 1; document.write(cntSubstr(str, K)); // This code is contributed by Potta Lokesh </script> |
Output
7
Time Complexity: O(N)
Auxiliary Space: O(N)
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!