Count all sub-strings with weight of characters atmost K

0 0 5 minutes read

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 K
int 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 code
int 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 K
import java.util.*;
 
class GFG{
  
// Function to find the count of
// all the subStrings with weight
// of characters atmost K
static 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 code
public 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 = 5
N = 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 K
using System;
using System.Collections.Generic;
 
class GFG{
   
// Function to find the count of
// all the subStrings with weight
// of characters atmost K
static 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 code
public 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 K
function 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:

Time Complexity: 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 zambiatek!