Longitud de la substring recurrente formada por caracteres repetidos que multiplican su índice en el rango [L, R] para consultas Q

Dada una string S y dos enteros L y R . La tarea es encontrar la longitud de la substring en el rango dado de modo que cada carácter se repita después de sí mismo exactamente k veces, donde k es el índice del carácter correspondiente en el alfabeto. Imprimir el resultado deseado para q consultas

Ejemplos :

Entrada : s = “cbbde”, q = 3, consultas[] = { { 2, 4 }, { 3, 5 }, { 1, 3 } };
Salida : {8, 7, 11}
Explicación : substring después de repetirse en el rango dado: «bbddddeeeee». Entonces, longitud de la substring = 11

Entrada : s = “xyyz”, q = 1, consultas[] = {1, 2}
Salida : 49

 

Enfoque : El enfoque implica la idea de precálculo para resolver cada consulta en O(1). 

  • Primero, cree la string repitiendo los caracteres por sus índices.
  • Calcule previamente la longitud de la substring recurrente para el rango [0, i] para cada carácter en la string formada.
  • Con la ayuda de una array de prefijos, almacene la suma de los valores correspondientes, a los que apunta el carácter actual, en los alfabetos.
  • Para cada consulta, determine la longitud de la substring recurrente e imprima el resultado en O(1)

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of
// recurring substring in range [l, r]
int recurringSubstring(string s, int l, int r)
{
 
    // Length of the string
    int N = s.size();
 
    // Variable to store the index of
    // the character in the alphabet
    int a[N];
    for (int i = 0; i < N; i++) {
 
        a[i] = (s[i] - 'a') + 1;
    }
 
    // Prefix array to store the sum
    int prefix[N];
    prefix[0] = a[0];
 
    for (int i = 1; i < N; i++) {
 
        prefix[i] = prefix[i - 1] + a[i];
    }
 
    l = l - 1;
    r = r - 1;
 
    // If l is greater than 0
    if (l != 0) {
 
        return prefix[r] - prefix[l - 1];
    }
 
    // If l is less or equal to 0
    else {
 
        return prefix[r];
    }
}
 
void recurSubQueries(string s,
                     pair<int, int> queries[],
                     int q)
{
    for (int i = 0; i < q; i++) {
        int l = queries[i].first;
        int r = queries[i].second;
        cout << recurringSubstring(s, l, r)
             << endl;
    }
}
 
// Driver Code
int main()
{
 
    string s = "cbbde";
    int q = 3;
    pair<int, int> queries[]
        = { { 2, 4 }, { 3, 5 }, { 1, 3 } };
 
    recurSubQueries(s, queries, q);
 
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
 
class GFG
{
   
    // Function to find the length of
    // recurring substring in range [l, r]
    static int recurringSubstring(String s, int l, int r)
    {
 
        // Length of the string
        int N = s.length();
 
        // Variable to store the index of
        // the character in the alphabet
        int a[] = new int[N];
        for (int i = 0; i < N; i++) {
 
            a[i] = (s.charAt(i) - 'a') + 1;
        }
 
        // Prefix array to store the sum
        int prefix[] = new int[N];
        prefix[0] = a[0];
 
        for (int i = 1; i < N; i++) {
 
            prefix[i] = prefix[i - 1] + a[i];
        }
 
        l = l - 1;
        r = r - 1;
 
        // If l is greater than 0
        if (l != 0) {
 
            return prefix[r] - prefix[l - 1];
        }
 
        // If l is less or equal to 0
        else {
 
            return prefix[r];
        }
    }
 
    static void recurSubQueries(String s, int queries[][],
                                int q)
    {
        for (int i = 0; i < q; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            System.out.println(recurringSubstring(s, l, r));
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String s = "cbbde";
        int q = 3;
        int[][] queries = { { 2, 4 }, { 3, 5 }, { 1, 3 } };
 
        recurSubQueries(s, queries, q);
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python code for the above approach
 
# Function to find the length of
# recurring substring in range [l, r]
def recurringSubstring(s, l, r):
   
    # Length of the string
    N = len(s);
 
    # Variable to store the index of
    # the character in the alphabet
    a = [0 for i in range(N)];
 
    for i in range(N):
        a[i] = ord(s[i]) - ord('a') + 1;
 
    # Prefix array to store the sum
    prefix = [0 for i in range(N)];
    prefix[0] = a[0];
 
    for i in range(N):
        prefix[i] = prefix[i - 1] + a[i];
 
    l = l - 1;
    r = r - 1;
 
    # If l is greater than 0
    if (l != 0):
 
        return prefix[r] - prefix[l - 1];
 
 
    # If l is less or equal to 0
    else:
 
        return prefix[r];
 
def recurSubQueries(s, queries, q):
    for i in range(q):
        l = queries[i][0];
        r = queries[i][1];
        print(recurringSubstring(s, l, r));
 
# Driver Code
if __name__ == '__main__':
    s = "cbbde";
    q = 3;
    queries = [[2, 4], [3, 5], [1, 3]];
 
    recurSubQueries(s, queries, q);
 
# This code is contributed by 29AjayKumar

C#

// C# code for the above approach
using System;
 
public class GFG
{
   
    // Function to find the length of
    // recurring substring in range [l, r]
    static int recurringSubstring(String s, int l, int r)
    {
 
        // Length of the string
        int N = s.Length;
 
        // Variable to store the index of
        // the character in the alphabet
        int []a = new int[N];
        for (int i = 0; i < N; i++) {
 
            a[i] = (s[i] - 'a') + 1;
        }
 
        // Prefix array to store the sum
        int []prefix = new int[N];
        prefix[0] = a[0];
 
        for (int i = 1; i < N; i++) {
 
            prefix[i] = prefix[i - 1] + a[i];
        }
 
        l = l - 1;
        r = r - 1;
 
        // If l is greater than 0
        if (l != 0) {
 
            return prefix[r] - prefix[l - 1];
        }
 
        // If l is less or equal to 0
        else {
 
            return prefix[r];
        }
    }
 
    static void recurSubQueries(String s, int [,]queries,
                                int q)
    {
        for (int i = 0; i < q; i++) {
            int l = queries[i,0];
            int r = queries[i,1];
            Console.WriteLine(recurringSubstring(s, l, r));
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String s = "cbbde";
        int q = 3;
        int[,] queries = { { 2, 4 }, { 3, 5 }, { 1, 3 } };
 
        recurSubQueries(s, queries, q);
    }
}
 
 
// This code is contributed by shikhasingrajput

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find the length of
    // recurring substring in range [l, r]
    const recurringSubstring = (s, l, r) => {
 
        // Length of the string
        let N = s.length;
 
        // Variable to store the index of
        // the character in the alphabet
        let a = new Array(N).fill(0);
        for (let i = 0; i < N; i++) {
 
            a[i] = (s.charCodeAt(i) - 'a'.charCodeAt(0)) + 1;
        }
 
        // Prefix array to store the sum
        let prefix = new Array(N).fill(0);
        prefix[0] = a[0];
 
        for (let i = 1; i < N; i++) {
 
            prefix[i] = prefix[i - 1] + a[i];
        }
 
        l = l - 1;
        r = r - 1;
 
        // If l is greater than 0
        if (l != 0) {
 
            return prefix[r] - prefix[l - 1];
        }
 
        // If l is less or equal to 0
        else {
 
            return prefix[r];
        }
    }
 
    const recurSubQueries = (s, queries, q) => {
        for (let i = 0; i < q; i++) {
            let l = queries[i][0];
            let r = queries[i][1];
            document.write(`${recurringSubstring(s, l, r)}<br/>`);
        }
    }
 
    // Driver Code
    let s = "cbbde";
    let q = 3;
    let queries = [[2, 4], [3, 5], [1, 3]];
 
    recurSubQueries(s, queries, q);
 
    // This code is contributed by rakeshsahni
 
</script>
Producción

8
11
7

Complejidad de tiempo : O(N+Q), donde N es la longitud de la string
Espacio auxiliar : O(N)

Publicación traducida automáticamente

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