Dada una string S de longitud N y un rango [L, R] (1 <= L, R <= N). La tarea es encontrar la longitud de la string formada al repetir cada carácter en el rango [L, R] , multiplicado por su valor lexicográfico .
Ejemplos:
Entrada: s = “cbbde”, l = 2, r = 5
Salida: 13
Explicación: La string resultante se forma después de repetir cada carácter en el rango [2, 5] como se muestra a continuación:
b repetido 2 veces
b repetido 2 veces
d repetido 4 veces
e repetido 5 veces
String resultante: ‘bbbbddddeeeee’
Por lo tanto, la longitud de la string resultante así formada es 13Entrada: s = “xyyz”, l = 1, r = 2
Salida: 49
Enfoque nativo: la tarea se puede resolver formando una string temporal , agregando caracteres lexicográficos repetidos veces en el rango [L, R] y, finalmente, devolviendo la longitud de la string resultante.
Complejidad de tiempo : O((R-L+1) * 26)
Espacio auxiliar : O((R-L+1) * 26)
Enfoque eficiente: la tarea se puede resolver con la ayuda de una array de prefijos , que almacenará la suma de los valores lexicográficos correspondientes.
Siga los pasos a continuación para resolver el problema:
- Cree una array de prefijos ‘ prefijo ‘, para almacenar la suma acumulativa del valor lexicográfico del carácter actual
- Para obtener la respuesta dada [L, R]: encuentre la diferencia de prefijo [R] y prefijo [L-1] , si L > 0 y prefijo [L] , si L = 0, para obtener la respuesta de la ventana ( R-L+1 ).
- Nota : este enfoque funciona de manera eficiente en caso de consultas múltiples.
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];
}
}
// Driver Code
int main()
{
string s = "cbbde";
int l = 2, r = 5;
cout << recurringSubstring(s, l, r);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
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.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];
}
}
// Driver Code
public static void main(String args[])
{
String s = "cbbde";
int l = 2, r = 5;
System.out.println(recurringSubstring(s, l, r));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program 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] * N
for i in range(N):
a[i] = (ord(s[i]) - ord('a')) + 1
# Prefix array to store the sum
prefix = [0] * N
prefix[0] = a[0]
for i in range(1, 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]
# Driver Code
s = "cbbde"
l = 2
r = 5
print(recurringSubstring(s, l, r))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
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];
}
}
// Driver Code
public static void Main()
{
string s = "cbbde";
int l = 2, r = 5;
Console.Write(recurringSubstring(s, l, r));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find the length of
// recurring substring in range [l, r]
function 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 = [];
for (let i = 0; i < N; i++) {
a[i] = (s.charCodeAt(s[i]) - s.charCodeAt('a')) + 1;
}
// Prefix array to store the sum
let prefix = [];
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];
}
}
// Driver Code
let s = "cbbde";
let l = 2, r = 5;
document.write(recurringSubstring(s, l, r));
// This code is contributed by Samim Hossain Mondal
</script>
Producción
13
Complejidad de tiempo : O(N), donde N es la longitud de la string
Espacio auxiliar : O(N)
Enfoque de espacio optimizado : el enfoque anterior se puede optimizar aún más eliminando la array de prefijos y simplemente iterando sobre el rango dado y agregando los valores lexicográficos correspondientes a la respuesta.
Siga los pasos a continuación para resolver el problema:
- Itere sobre el rango [L, R] y agregue los valores lexicográficos correspondientes a la respuesta.
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();
// Length of resultant string
int ans = 0;
for (int i = l - 1; i <= r - 1; i++) {
// Add lexicographic value of s[i]
ans += (s[i] - 'a' + 1);
}
return ans;
}
// Driver Code
int main()
{
string s = "cbbde";
int l = 2, r = 5;
cout << recurringSubstring(s, l, r);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
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();
// Length of resultant string
int ans = 0;
for (int i = l - 1; i <= r - 1; i++) {
// Add lexicographic value of s[i]
ans += (s.charAt(i) - 'a' + 1);
}
return ans;
}
// Driver Code
public static void main(String args[])
{
String s = "cbbde";
int l = 2, r = 5;
System.out.println(recurringSubstring(s, l, r));
}
}
// This code is contributed by Samim Hossain Mondal.
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)
# Length of resultant string
ans = 0
for i in range(l-1, r):
# Add lexicographic value of s[i]
ans = ans + (ord(s[i]) - ord('a') + 1)
return ans
# Driver Code
s = "cbbde"
l = 2
r = 5
print(recurringSubstring(s, l, r))
# This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
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;
// Length of resultant string
int ans = 0;
for (int i = l - 1; i <= r - 1; i++) {
// Add lexicographic value of s[i]
ans += (s[i] - 'a' + 1);
}
return ans;
}
// Driver Code
public static void Main()
{
string s = "cbbde";
int l = 2, r = 5;
Console.Write(recurringSubstring(s, l, r));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find the length of
// recurring substring in range [l, r]
function recurringSubstring(s, l, r)
{
// Length of the string
let N = s.length;
// Length of resultant string
let ans = 0;
for (let i = l - 1; i <= r - 1; i++) {
// Add lexicographic value of s[i]
ans += (s.charCodeAt(s[i]) - s.charCodeAt('a') + 1);
}
return ans;
}
// Driver Code
let s = "cbbde";
let l = 2, r = 5;
document.write(recurringSubstring(s, l, r));
// This code is contributed by Samim Hossain Mondal
</script>
Producción
13
Complejidad de tiempo : O(N), donde N es la longitud de la string
Espacio auxiliar : O(1)