Consultas de frecuencias de caracteres en substrings

Posted on by Rudeus Greyrat

Dada una string s y Q número de consultas. Cada consulta Q consta de l y r y un carácter c. Encuentre la frecuencia del carácter c en la substring l a r.
Ejemplos: 
 

Input : s = geeksforgeeks
        4
        0 5 e
        2 6 f
        4 7 m
        0 12 e
Output : 2
         1
         0
         4
Substring from 0 to 5 is geeksf.
Here e occurs 2 times.

Input : s = apple
        2
        0 4 e
        1 2 p        
Output : 1
         2

Enfoque ingenuo: ejecute un ciclo de l a r para Q número de consultas. Cuente la aparición del carácter y devuelva el recuento. La complejidad del tiempo total será Q * O(|s|).
Enfoque eficiente: podemos calcular previamente el recuento de cada carácter. Almacene el recuento de cada carácter en una array 2-D. Devuelve la frecuencia del carácter de 0 a r menos la frecuencia del carácter en el rango de 0 a l en O(1). La complejidad del tiempo total será Q * O(1).
 

C++

// CPP program to find occurrence
// of character in substring l to r
#include <bits/stdc++.h>
#define MAX_LEN 1005
#define MAX_CHAR 26
 
using namespace std;
 
// To store count of all character
int cnt[MAX_LEN][MAX_CHAR];
 
// To pre-process string from
// 0 to size of string
void preProcess(string s)
{
    int n = s.length();
 
    // Initializing cnt with 0
    memset(cnt, 0, sizeof(cnt));
 
    // Store occurrence of
    // character i
    for (int i = 0; i < n; i++)
        cnt[i][s[i] - 'a']++;
 
    // Store occurrence o
    // all character upto i
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 26; j++)
            cnt[i][j] += cnt[i - 1][j];
    }
}
 
// To return occurrence of
// character in range l to r
int findCharFreq(int l, int r, char c)
{
    // Return occurrence of character
    // from 0 to r minus its
    // occurrence from 0 to l
    int count = cnt[r][c-'a'];
   
    if (l != 0)
        count -= cnt[l - 1][c-'a'];
    return count;
}
 
// Driver program to test above functions
int main()
{
    string s = "geeksforgeeks";
    int Q = 4;
    preProcess(s);
 
    cout << findCharFreq(0, 5, 'e') << endl;
    cout << findCharFreq(2, 6, 'f') << endl;
    cout << findCharFreq(4, 7, 'm') << endl;
    cout << findCharFreq(0, 12, 'e') << endl;
 
    return 0;
}

Java

// Java program to find occurrence
// of character in substring l to r
import java.util.*;
 
class GFG
{
 
static int MAX_LEN = 1005;
static int MAX_CHAR = 26;
 
// To store count of all character
static int [][]cnt = new int[MAX_LEN][MAX_CHAR];
 
// To pre-process string from
// 0 to size of string
static void preProcess(String s)
{
    int n = s.length();
 
    // Store occurrence of
    // character i
    for (int i = 0; i < n; i++)
        cnt[i][s.charAt(i) - 'a']++;
 
    // Store occurrence o
    // all character upto i
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 26; j++)
            cnt[i][j] += cnt[i - 1][j];
    }
}
 
// To return occurrence of
// character in range l to r
static int findCharFreq(int l, int r, char c)
{
    // Return occurrence of character
    // from 0 to r minus its
    // occurrence from 0 to l
    return (cnt[r][(c) - 97] - cnt[l][(c) - 97]);
}
 
// Driver Code
public static void main(String[] args)
{
    String s = "geeksforgeeks";
    int Q = 4;
    preProcess(s);
 
    System.out.println(findCharFreq(0, 5, 'e'));
    System.out.println(findCharFreq(2, 6, 'f'));
    System.out.println(findCharFreq(4, 7, 'm'));
    System.out.println(findCharFreq(0, 12, 'e'));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find occurrence
# of character in substring l to r
MAX_LEN, MAX_CHAR = 1005, 26
 
# To store count of all character
cnt = [[0 for i in range(MAX_CHAR)]
          for j in range(MAX_LEN)]
 
# To pre-process string from
# 0 to size of string
def preProcess(s):
 
    n = len(s)
 
    # Store occurrence of character i
    for i in range(0, n):
        cnt[i][ord(s[i]) - ord('a')] += 1
 
    # Store occurrence o
    # all character upto i
    for i in range(1, n):
        for j in range(0, 26):
            cnt[i][j] += cnt[i - 1][j]
     
# To return occurrence of
# character in range l to r
def findCharFreq(l, r, c):
 
    # Return occurrence of character
    # from 0 to r minus its
    # occurrence from 0 to l
    return (cnt[r][ord(c) - 97] -
            cnt[l - 1][ord(c) - 97])
 
# Driver Code
if __name__ == "__main__":
 
    s = "geeksforgeeks"
    Q = 4
    preProcess(s)
 
    print(findCharFreq(0, 5, 'e'))
    print(findCharFreq(2, 6, 'f'))
    print(findCharFreq(4, 7, 'm'))
    print(findCharFreq(0, 12, 'e'))
 
# This code is contributed by Rituraj Jain
# and Edited by Md Azharuddin

C#

// C# program to find occurrence
// of character in substring l to r
using System;
 
class GFG
{
    static int MAX_LEN = 1005;
    static int MAX_CHAR = 26;
 
    // To store count of all character
    static int[,] cnt = new int[MAX_LEN,
                                MAX_CHAR];
 
    // To pre-process string from
    // 0 to size of string
    static void preProcess(string s)
    {
        int n = s.Length;
 
        // Store occurrence of
        // character i
        for (int i = 0; i < n; i++)
            cnt[i, s[i] - 'a']++;
 
        // Store occurrence o
        // all character upto i
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < 26; j++)
                cnt[i, j] += cnt[i - 1, j];
        }
    }
 
    // To return occurrence of
    // character in range l to r
    static int findCharFreq(int l, int r, char c)
    {
        // Return occurrence of character
        // from 0 to r minus its
        // occurrence from 0 to l
        return (cnt[r, c - 97] - cnt[l, c - 97]);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        string s = "geeksforgeeks";
        int Q = 4;
        preProcess(s);
 
        Console.WriteLine(findCharFreq(0, 5, 'e'));
        Console.WriteLine(findCharFreq(2, 6, 'f'));
        Console.WriteLine(findCharFreq(4, 7, 'm'));
        Console.WriteLine(findCharFreq(0, 12, 'e'));
    }
}
 
// This code is contributed by
// sanjeev2552

Javascript

<script>
 
// JavaScript program to find occurrence
// of character in substring l to r
const MAX_LEN = 1005, MAX_CHAR = 26
 
// To store count of all character
let cnt = new Array(MAX_LEN);
 
for(let i = 0;i < MAX_LEN;i++){
    cnt[i] = new Array(MAX_CHAR).fill(0);
}
 
// To pre-process string from
// 0 to size of string
function preProcess(s){
 
    let n = s.length
 
    // Store occurrence of character i
    for(let i=0;i<n;i++){
        cnt[i][s.charCodeAt(i) - 'a'.charCodeAt(0)] += 1
    }
 
    // Store occurrence o
    // all character upto i
    for(let i=1;i<n;i++)
        for(let j=0;j<26;j++)
            cnt[i][j] += cnt[i - 1][j]
}
     
// To return occurrence of
// character in range l to r
function findCharFreq(l, r, c){
 
    // Return occurrence of character
    // from 0 to r minus its
    // occurrence from 0 to l
    let count = cnt[r][c.charCodeAt(0) - 97]
    
    if (l != 0)
        count -= cnt[l - 1][c.charCodeAt(0) - 97]
    return count
}
 
// Driver Code
 
let s = "geeksforgeeks"
let Q = 4
preProcess(s)
 
document.write(findCharFreq(0, 5, 'e'),"</br>")
document.write(findCharFreq(2, 6, 'f'),"</br>")
document.write(findCharFreq(4, 7, 'm'),"</br>")
document.write(findCharFreq(0, 12, 'e'),"</br>")
 
// This code is contributed by shinjanpatra
 
<script>

Producción: 
 

2
1
0
4

Publicación traducida automáticamente

Artículo escrito por nuclode 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 *