Recuento de todas las substrings con suma de pesos como máximo K

Dada una string S que consiste en letras minúsculas en inglés y una string W que consiste en el peso de todos los caracteres del alfabeto inglés donde para todo i,

$0 \leq Qi \leq 9$

. Tenemos que encontrar los números totales de una substring única con una suma de pesos como máximo K.
Ejemplos:

Entrada: P = “ababab”, Q = “12345678912345678912345678”, K=5
Salida: 7
Explicación:
Las substrings únicas son: “a”, “ab”, “b”, “bc”, “c”, “d” , “e”
Por lo tanto, la cuenta es 7.

Entrada: P = “acbacbacaa”, Q = “12300045600078900012345000”, K=2
Salida: 3
Explicación: Las substrings únicas son: “a”, “b”, “aa”
Por lo tanto, el recuento es 3.

Enfoque:
para resolver el problema anterior, la idea principal es simplemente iterar a través de todas las substrings y mantener una suma del peso de todos los caracteres encontrados hasta el momento. Si la suma de caracteres no es mayor que K, insértela en un hashmap; de lo contrario, deséchela y continúe con otra substring. Finalmente, el resultado será el tamaño del hashmap porque almacena todas las substrings que tienen un peso menor o igual a K.

A continuación se muestra la implementación del enfoque anterior:

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 substrings
int 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 code
int 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 substrings
def 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 code
if __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 code
static 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 substrings
function 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>

Producción:

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta