Given a string P consisting of small English letters and a string Q consisting of weight of all characters of English alphabet such that for all ‘i’, 0 ? Q[i] ? 9. The task is to find the total numbers of unique substring with sum of weights atmost K.
Examples:
Input: P = “ababab”, Q = “12345678912345678912345678”, K = 5
Output: 7
Explanation:
The substrings with the sum of weights of individual characters ? 5 are:
“a”, “ab”, “b”, “bc”, “c”, “d”, “e”
Input: P = “acbacbacaa”, Q = “12300045600078900012345000”, K = 2
Output: 3
Explanation:
The substrings with the sum of weights of individual characters ? 2 are:
“a”, “b”, “aa”
Approach: The idea is to use an unordered set to store the unique values. The following steps are followed to compute the answer:
- Iterate over all the substrings using the nested loops and maintain the sum of the weight of all the characters encountered so far.
- If the sum of characters is not greater than K, then insert it in a hashmap.
- Finally, output the size of the hashmap.
Below is the implementation of the above approach:
C++
// C++ program to find the count of// all the sub-strings with weight of// characters atmost K#include <bits/stdc++.h>using namespace std;// Function to find the count of// all the substrings with weight// of characters atmost Kint distinctSubstring(string& P, string& Q, int K, int N){ // Hashmap to store all substrings unordered_set<string> S; // Iterate over all substrings for (int i = 0; i < N; ++i) { // Maintain the sum of all characters // encountered so far int sum = 0; // Maintain the substring till the // current position string s; for (int j = i; j < N; ++j) { // Get the position of the // character in string Q int pos = P[j] - 'a'; // Add weight to current sum sum += Q[pos] - '0'; // Add current character to substring s += P[j]; // If sum of characters is <=K // then insert into the set if (sum <= K) { S.insert(s); } else { break; } } } // Finding the size of the set return S.size();}// Driver codeint main(){ string P = "abcde"; string Q = "12345678912345678912345678"; int K = 5; int N = P.length(); cout << distinctSubstring(P, Q, K, N); return 0;} |
Java
// Java program to find the count of// all the sub-Strings with weight of// characters atmost Kimport java.util.*;class GFG{ // Function to find the count of// all the subStrings with weight// of characters atmost Kstatic int distinctSubString(String P, String Q, int K, int N){ // Hashmap to store all subStrings HashSet<String> S = new HashSet<String>(); // Iterate over all subStrings for (int i = 0; i < N; ++i) { // Maintain the sum of all characters // encountered so far int sum = 0; // Maintain the subString till the // current position String s = ""; for (int j = i; j < N; ++j) { // Get the position of the // character in String Q 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); // If sum of characters is <=K // then insert into the set if (sum <= K) { S.add(s); } else { break; } } } // Finding the size of the set return S.size();} // Driver codepublic static void main(String[] args){ String P = "abcde"; String Q = "12345678912345678912345678"; int K = 5; int N = P.length(); System.out.print(distinctSubString(P, Q, K, N));}}// This code is contributed by Rajput-Ji |
Python3
# Python program to find the count of # all the sub-strings with weight of # characters atmost K# Function to find the count of # all the substrings with weight # of characters atmost K def distinctSubstring(P, Q, K, N): # Hashmap to store all substrings S = set() # Iterate over all substrings for i in range(0,N): # Maintain the sum of all characters # encountered so far sum = 0; # Maintain the substring till the # current position s = '' for j in range(i,N): # Get the position of the # character in string Q pos = ord(P[j]) - 97 # Add weight to current sum sum = sum + ord(Q[pos]) - 48 # Add current character to substring s += P[j] # If sum of characters is <=K # then insert into the set if (sum <= K): S.add(s) else: break # Finding the size of the set return len(S)# Driver code P = "abcde"Q = "12345678912345678912345678"K = 5N = len(P)print(distinctSubstring(P, Q, K, N))# This code is contributed by Sanjit_Prasad |
C#
// C# program to find the count of// all the sub-Strings with weight of// characters atmost Kusing System;using System.Collections.Generic;class GFG{ // Function to find the count of// all the subStrings with weight// of characters atmost Kstatic int distinctSubString(String P, String Q, int K, int N){ // Hashmap to store all subStrings HashSet<String> S = new HashSet<String>(); // Iterate over all subStrings for (int i = 0; i < N; ++i) { // c the sum of all characters // encountered so far int sum = 0; // Maintain the subString till the // current position String s = ""; for (int j = i; j < N; ++j) { // Get the position of the // character in String Q int pos = P[j] - 'a'; // Add weight to current sum sum += Q[pos] - '0'; // Add current character to subString s += P[j]; // If sum of characters is <=K // then insert into the set if (sum <= K) { S.Add(s); } else { break; } } } // Finding the size of the set return S.Count;} // Driver codepublic static void Main(String[] args){ String P = "abcde"; String Q = "12345678912345678912345678"; int K = 5; int N = P.Length; Console.Write(distinctSubString(P, Q, K, N));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find the count of// all the sub-Strings with weight of// characters atmost K// Function to find the count of// all the subStrings with weight// of characters atmost Kfunction distinctSubString(P, Q, K, N){ // Hashmap to store all subStrings let S = new Set(); // Iterate over all subStrings for (let i = 0; i < N; ++i) { // Maintain the sum of all characters // encountered so far let sum = 0; // Maintain the subString till the // current position let s = ""; for (let j = i; j < N; ++j) { // Get the position of the // character in String Q 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]; // If sum of characters is <=K // then insert into the set if (sum <= K) { S.add(s); } else { break; } } } // Finding the size of the set return S.size;} // Driver code let P = "abcde"; let Q = "12345678912345678912345678"; let K = 5; let N = P.length; document.write(distinctSubString(P, Q, K, N)); </script> |
Output:
7
Time Complexity: O(N2)
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!
