Given a string S consisting of small English letters and a string W consisting of weight of all characters of English alphabet where for all i,
. We have to find the total numbers of a unique substring with sum of weights at most K.
Examples:
Input : P = “ababab”, Q = “12345678912345678912345678”, K=5
Output : 7
Explanation :
The unique substrings are: “a”, “ab”, “b”, “bc”, “c”, “d”, “e”
Hence, the count is 7.Input : P = “acbacbacaa”, Q = “12300045600078900012345000”, K=2
Output : 3
Explanation :The unique substrings are: “a”, “b”, “aa”
Hence, the count is 3.
Approach:
To solve the above problem, the main idea is to simply iterate through all the substrings and maintain a sum of the weight of all characters encountered so far. If the sum of characters is not greater than K, then insert it in a hashmap otherwise discard it and move forward with another substring. Finally, the result will be the size of the hashmap because it stores all the substring which have weight less than or equal to K.
Below is the implementation of the above approach:
C++
// C++ implementation to Count all// sub-strings with sum of weights at most K#include <bits/stdc++.h>using namespace std;// Function to count all substringsint distinctSubstring(string& P, string& Q, int K, int N){ // Hashmap to store substrings unordered_set<string> S; // iterate over all substrings for (int i = 0; i < N; ++i) { // variable to maintain sum // of all characters encountered int sum = 0; // variable to maintain // substring till current position string s; for (int j = i; j < N; ++j) { // get position of // character in string W int pos = P[j] - 'a'; // add weight to current sum sum += Q[pos] - '0'; // add current character to substring s += P[j]; // check if sum of characters // is <=K insert in Hashmap if (sum <= K) { S.insert(s); } else { break; } } } return S.size();}// Driver codeint main(){ // initialise string string S = "abcde"; // initialise weight string W = "12345678912345678912345678"; int K = 5; int N = S.length(); cout << distinctSubstring(S, W, K, N); return 0;} |
Java
// Java implementation to count all // sub-strings with sum of weights at most K import java.io.*;import java.util.*; class GFG{// Function to count all substrings static int distinctSubstring(String P, String Q, int K, int N) { // Hashmap to store substrings Set<String> S = new HashSet<>(); // Iterate over all substrings for(int i = 0; i < N; ++i) { // Variable to maintain sum // of all characters encountered int sum = 0; // Variable to maintain substring // till current position String s = ""; for(int j = i; j < N; ++j) { // Get position of // character in string W int pos = P.charAt(j) - 'a'; // Add weight to current sum sum += Q.charAt(pos) - '0'; // Add current character to substring s += P.charAt(j); // Check if sum of characters // is <=K insert in Hashmap if (sum <= K) { S.add(s); } else { break; } } } return S.size(); } // Driver Code public static void main(String args[]){ // Initialise string String S = "abcde"; // Initialise weight String W = "12345678912345678912345678"; int K = 5; int N = S.length(); System.out.println(distinctSubstring(S, W, K, N)); }} // This code is contributed by offbeat |
Python3
# Python3 implementation to Count all# sub-strings with sum of weights at most K# Function to count all substringsdef distinctSubstring(P, Q, K, N): # Hashmap to store substrings S = set() # iterate over all substrings for i in range(N): # variable to maintain sum # of all characters encountered sum = 0 # variable to maintain # substring till current position s = "" for j in range(i, N): # get position of # character in string W pos = ord(P[j]) - 97 # add weight to current sum sum += ord(Q[pos]) - 48 # add current character to substring s += P[j] # check if sum of characters # is <=K insert in Hashmap if (sum <= K): S.add(s) else: break return len(S)# Driver codeif __name__ == '__main__': # initialise string S = "abcde" # initialise weight W = "12345678912345678912345678" K = 5 N = len(S) print(distinctSubstring(S, W, K, N))# This code is contributed by Surendra_Gangwar |
C#
// C# implementation to count all sub-strings // with sum of weights at most K using System;using System.Collections.Generic; class GFG{ // Function to count all substrings static int distinctSubstring(string P, string Q, int K, int N) { // Hashmap to store substrings HashSet<string> S = new HashSet<string>(); // Iterate over all substrings for(int i = 0; i < N; ++i) { // Variable to maintain sum // of all characters encountered int sum = 0; // Variable to maintain substring // till current position string s = ""; for(int j = i; j < N; ++j) { // Get position of // character in string W int pos = P[j] - 'a'; // Add weight to current sum sum += Q[pos] - '0'; // Add current character to // substring s += P[j]; // Check if sum of characters // is <=K insert in Hashmap if (sum <= K) { S.Add(s); } else { break; } } } return S.Count; } // Driver codestatic void Main() { // Initialise string string S = "abcde"; // Initialise weight string W = "12345678912345678912345678"; int K = 5; int N = S.Length; Console.WriteLine(distinctSubstring(S, W, K, N)); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript implementation to count all// sub-strings with sum of weights at most K// Function to count all substringsfunction distinctSubstring(P, Q, K, N){ // Hashmap to store substrings let S = new Set(); // Iterate over all substrings for(let i = 0; i < N; ++i) { // Variable to maintain sum // of all characters encountered let sum = 0; // Variable to maintain substring // till current position let s = ""; for(let j = i; j < N; ++j) { // Get position of // character in string W let pos = P[j].charCodeAt() - 'a'.charCodeAt(); // Add weight to current sum sum += Q[pos].charCodeAt() - '0'.charCodeAt(); // Add current character to substring s += P[j]; // Check if sum of characters // is <=K insert in Hashmap if (sum <= K) { S.add(s); } else { break; } } } return S.size;} // Driver code // Initialise string let S = "abcde"; // Initialise weight let W = "12345678912345678912345678"; let K = 5; let N = S.length; document.write(distinctSubstring(S, W, K, N)); </script> |
Output:
7
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!
