Longitud de la string formada por la repetición de cada carácter en el rango [L, R] de la string dada multiplicada por su valor lexicográfico

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 13

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

Publicación traducida automáticamente

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