Given a string str and Q queries. Each query consists of an integer K. The task is to find the number of ways of choosing K equal sub-strings of any length possible for every query. Note that the set of K substrings must be unique.
Examples:
Input: str = “aabaab”, que[] = {3}
Output: 4
“a” is the only sub-string that appears more than 3 times i.e. 4.
And there are 4 ways of choosing 3 different strings from the given 4 strings.
Input: str = “aggghh”, que[] = {1, 2, 3}
Output:
21
5
1
Approach: The following steps can be followed to solve the problem and answer every query in the minimal possible time.
- Generate all the substrings for a string and count the occurrence of every unique substring using hashing.
- For every query, the answer will to choose K substrings of every string which occurs for more than K times(say X). The answer will be
- The time complexity per query can be reduced by pre-computing the binomial co-efficient
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define maxlen 100// Function to generate all the sub-stringsvoid generateSubStrings(string s, unordered_map<string, int>& mpp){ // Length of the string int l = s.length(); // Generate all sub-strings for (int i = 0; i < l; i++) { string temp = ""; for (int j = i; j < l; j++) { temp += s[j]; // Count the occurrence of // every sub-string mpp[temp] += 1; } }}// Compute the Binomial Coefficientvoid binomialCoeff(int C[maxlen][maxlen]){ int i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 0; i < 100; i++) { for (j = 0; j < 100; j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } }}// Function to return the result for a queryint answerQuery(unordered_map<string, int>& mpp, int C[maxlen][maxlen], int k){ int ans = 0; // Iterate for every // unique sub-string for (auto it : mpp) { // Count the combinations if (it.second >= k) ans += C[it.second][k]; } return ans;}// Driver codeint main(){ string s = "aabaab"; // Get all the sub-strings // Store the occurrence of // all the sub-strings unordered_map<string, int> mpp; generateSubStrings(s, mpp); // Pre-computation int C[maxlen][maxlen]; memset(C, 0, sizeof C); binomialCoeff(C); // Queries int queries[] = { 2, 3, 4 }; int q = sizeof(queries) / sizeof(queries[0]); // Perform queries for (int i = 0; i < q; i++) cout << answerQuery(mpp, C, queries[i]) << endl; return 0;} |
Java
// Java implementation of the approach import java.util.HashMap;class GFG { static int maxlen = 100; // Function to generate all the sub-strings public static void generateSubStrings( String s, HashMap<String, Integer> mpp) { // Length of the string int l = s.length(); // Generate all sub-strings for (int i = 0; i < l; i++) { String temp = ""; for (int j = i; j < l; j++) { temp += s.charAt(j); // Count the occurrence of // every sub-string if (mpp.containsKey(temp)) { int x = mpp.get(temp); mpp.put(temp, ++x); } else mpp.put(temp, 1); } } } // Compute the Binomial Coefficient public static void binomialCoeff(int[][] C) { int i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 1; i < 100; i++) { for (j = 0; j < 100; j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } } // Function to return the result for a query public static int answerQuery(HashMap<String, Integer> mpp, int[][] C, int k) { int ans = 0; // Iterate for every // unique sub-string for (HashMap.Entry<String, Integer> entry : mpp.entrySet()) { // Count the combinations if (entry.getValue() >= k) ans += C[entry.getValue()][k]; } return ans; } // Driver code public static void main(String[] args) { String s = "aabaab"; // Get all the sub-strings // Store the occurrence of // all the sub-strings HashMap<String, Integer> mpp = new HashMap<>(); generateSubStrings(s, mpp); // Pre-computation int[][] C = new int[maxlen][maxlen]; binomialCoeff(C); // Queries int[] queries = { 2, 3, 4 }; int q = queries.length; // Perform queries for (int i = 0; i < q; i++) System.out.println(answerQuery(mpp, C, queries[i])); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the approach from collections import defaultdictmaxlen = 100# Function to generate all the sub-strings def generateSubStrings(s, mpp): # Length of the string l = len(s) # Generate all sub-strings for i in range(0, l): temp = "" for j in range(i, l): temp += s[j] # Count the occurrence of # every sub-string mpp[temp] += 1# Compute the Binomial Coefficient def binomialCoeff(C): # Calculate value of Binomial # Coefficient in bottom up manner for i in range(0, 100): for j in range(0, 100): # Base Cases if j == 0 or j == i: C[i][j] = 1 # Calculate value using previously # stored values else: C[i][j] = C[i - 1][j - 1] + C[i - 1][j] # Function to return the result for a query def answerQuery(mpp, C, k): ans = 0 # Iterate for every # unique sub-string for it in mpp: # Count the combinations if mpp[it] >= k: ans += C[mpp[it]][k] return ans # Driver code if __name__ == "__main__": s = "aabaab" # Get all the sub-strings # Store the occurrence of # all the sub-strings mpp = defaultdict(lambda:0) generateSubStrings(s, mpp) # Pre-computation C = [[0 for i in range(maxlen)] for j in range(maxlen)] binomialCoeff(C) # Queries queries = [2, 3, 4] q = len(queries) # Perform queries for i in range(0, q): print(answerQuery(mpp, C, queries[i])) # This code is contributed by Rituraj Jain |
C#
// C# code to print level order // traversal in sorted orderusing System;using System.Collections.Generic;class GFG { static int maxlen = 100; // Function to generate all the sub-strings public static void generateSubStrings(String s, Dictionary<String, int> mpp) { // Length of the string int l = s.Length; // Generate all sub-strings for (int i = 0; i < l; i++) { String temp = ""; for (int j = i; j < l; j++) { temp += s[j]; // Count the occurrence of // every sub-string if (mpp.ContainsKey(temp)) { mpp[temp] = ++mpp[temp]; } else mpp.Add(temp, 1); } } } // Compute the Binomial Coefficient public static void binomialCoeff(int[,] C) { int i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 1; i < 100; i++) { for (j = 0; j < 100; j++) { // Base Cases if (j == 0 || j == i) C[i, j] = 1; // Calculate value using previously // stored values else C[i, j] = C[i - 1, j - 1] + C[i - 1, j]; } } } // Function to return the result for a query public static int answerQuery(Dictionary<String, int> mpp, int[,] C, int k) { int ans = 0; // Iterate for every // unique sub-string foreach(KeyValuePair<String, int> entry in mpp) { // Count the combinations if (entry.Value >= k) ans += C[entry.Value, k]; } return ans; } // Driver code public static void Main(String[] args) { String s = "aabaab"; // Get all the sub-strings // Store the occurrence of // all the sub-strings Dictionary<String, int> mpp = new Dictionary<String, int>(); generateSubStrings(s, mpp); // Pre-computation int[,] C = new int[maxlen, maxlen]; binomialCoeff(C); // Queries int[] queries = { 2, 3, 4 }; int q = queries.Length; // Perform queries for (int i = 0; i < q; i++) Console.WriteLine(answerQuery(mpp, C, queries[i])); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach let maxlen = 100;// Function to generate all the sub-stringsfunction generateSubStrings(s,mpp) { // Length of the string let l = s.length; // Generate all sub-strings for (let i = 0; i < l; i++) { let temp = ""; for (let j = i; j < l; j++) { temp += s[j]; // Count the occurrence of // every sub-string if (mpp.has(temp)) { let x = mpp.get(temp); mpp.set(temp, ++x); } else mpp.set(temp, 1); } }}// Compute the Binomial Coefficientfunction binomialCoeff(C){ let i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 1; i < 100; i++) { for (j = 0; j < 100; j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } }}// Function to return the result for a queryfunction answerQuery(mpp,C,k){ let ans = 0; // Iterate for every // unique sub-string for (let[key,value] of mpp.entries()) { // Count the combinations if (value >= k) ans += C[value][k]; } return ans;}// Driver codelet s = "aabaab";// Get all the sub-strings// Store the occurrence of// all the sub-stringslet mpp = new Map();generateSubStrings(s, mpp);// Pre-computationlet C = new Array(maxlen);for(let i=0;i<maxlen;i++){ C[i]=new Array(maxlen); for(let j=0;j<maxlen;j++) C[i][j]=0;}binomialCoeff(C);// Querieslet queries = [ 2, 3, 4 ];let q = queries.length;// Perform queriesfor (let i = 0; i < q; i++) document.write(answerQuery(mpp, C, queries[i])+"<br>");// This code is contributed by rag2127</script> |
Output:
10 4 1
Time Complexity: O(max(100*100, N*N)), as we are using nested loops for traversing N*N and 100*100 times. Where N is the length of the string.
Auxiliary Space: O(max(100*100,N*N)), as we are using extra space for map and matrix C. Where N is the length of the string.
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!
