Cuente todas las substrings con peso de caracteres como máximo K

Posted on by Rudeus Greyrat

Dada una string P que consiste en letras minúsculas en inglés y una string Q que consiste en el peso de todos los caracteres del alfabeto inglés tal que para todas las ‘i’, 0 ≤ Q[i] ≤ 9. La tarea es encontrar el número total de substrings únicas con suma de pesos como máximo K .
Ejemplos:

Entrada: P = “ababab”, Q = “12345678912345678912345678”, K = 5 
Salida: 7 
Explicación: 
Las substrings con la suma de los pesos de los caracteres individuales ≤ 5 son: 
“a”, “ab”, “b”, “bc ”, “c”, “d”, “e”
Entrada: P = “acbacbacaa”, Q = “12300045600078900012345000”, K = 2 
Salida: 3 
Explicación: 
Las substrings con la suma de los pesos de los caracteres individuales ≤ 2 son: 
“ a”, “b”, “aa” 
 

Enfoque: la idea es usar un conjunto desordenado para almacenar los valores únicos. Se siguen los siguientes pasos para calcular la respuesta: 
 

  • Iterar sobre todas las substrings utilizando los bucles anidados y mantener la 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.
  • Finalmente, genere el tamaño del hashmap.

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

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>
Producción: 

7

 

Complejidad del tiempo: O(N 2 )

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *