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 = 11Entrada : 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)