Substring más larga de caracteres dados reemplazando como máximo K caracteres para consultas Q

Dada una string s de longitud N y consultas Q , cada una de tipo (K, C) donde K es un número entero C es un carácter, la tarea es reemplazar como máximo K caracteres de la string por C y tener que imprimir el máximo longitud de la posible substring que contiene solo el carácter C . 

Ejemplos: 

Entrada: s = “yamatonadeshiko”, N= 15, Q = 10,  
consultas[] = {{1, a}, {2, a}, {3, a}, {4, a}, {5, a} , {1, b}, {2, b}, {3, b}, {4, b}, {5, b}}
Salida: 3, 4, 5, 7, 8, 1, 2, 3, 4 , 5
Explicación: En la primera consulta, «ama» puede convertirse en «aaa» por 1 reemplazo 
En la segunda consulta, «yama» puede convertirse en «aaaa», por lo que la respuesta es 4
En la tercera consulta, «yamat» puede convertirse en «aaaa» entonces la respuesta es 5
En la 4ta consulta «amatona» se puede hacer «aaaaaaa» entonces la respuesta es 7 
En la 5ta consulta «yamatona» se puede hacer «aaaaaaaa» entonces la respuesta es 8
En la 6ta consulta ya que no hay b ningún carácter diga “y” puede convertirse en “b” 
En la séptima consulta “ya” puede convertirse en “bb” 
En la octava consulta “yam” puede convertirse en “bbb” 
En la novena consulta, “yama” puede convertirse en “bbbb”
En la décima consulta, “yamat” puede convertirse en “bbbbb” 

Entrada: s = “koyomi”, N = 6, Q= 3, consultas[] = {{1, o}, {4, o}, {4, m}}
Salida: 3, 6, 5
Explicación: En el la primera consulta «oyo» se puede convertir en «ooo» usando 1 reemplazo.
En la segunda consulta, «koyomi» se puede convertir en «ooooo».
En la tercera consulta, «koyom» se puede hacer «mmmmm» usando 4 reemplazos «koyo».

Enfoque: La idea de resolver de manera eficiente este problema se basa en el concepto de programación dinámica :

Si podemos encontrar la substring más larga del carácter ‘ ch ‘ hasta el i ^-ésimo índice realizando j reemplazos, podemos encontrar fácilmente la substring más larga del carácter ch hasta (i+1) el índice realizando ^j reemplazos. Hay dos casos: 

1. i ^th carácter y ch son iguales y 
2. Ellos son diferentes.

Si esto se expresa matemáticamente como una función, podemos escribirlo como f(ch, i, j) . Entonces la longitud en los dos casos será:

1. Como son iguales, la longitud será uno más de lo que era hasta i ^th con j cambios. Entonces f(ch, i, j) = f(ch, i-1, j) + 1
2. Como son diferentes, la longitud será uno más de lo que era hasta el i ^-ésimo índice con cambios j-1 . Entonces f(ch, i, j) = f(ch, i-1, j-1) + 1

Por lo tanto, como máximo K cambia por el carácter C , es el máximo de todas las substrings más largas hasta cualquier índice para cualquier número de cambios en el rango [1, K] .

Siga los pasos mencionados a continuación para implementar la idea:

• Calcule previamente el resultado utilizando la programación dinámica y la relación como se mencionó anteriormente .
• Cree una array dp[][][] tridimensional para almacenar el resultado del cálculo previo.
• Calcule previamente el resultado de cualquier número de cambios para cualquier carácter para responder a las consultas en tiempo lineal:
  • Si la respuesta para ch con casi K cambios se representa como g(K, ch) entonces es el máximo de todos los valores de f(ch, i, K) donde i varía de (0 a N-1).
  • Use otra array bidimensional (digamos ans[][] ) para almacenar el resultado de g(K, ch) .
• Recorra las consultas y encuentre el valor de la array ans[][] .

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

// C++ code of above mentioned approach
 
#include <bits/stdc++.h>
using namespace std;
 
int dp[1001][1001][26];
int ans[1001][26];
 
// Precomputation to get the values
// of the function f() and g()
void preprocess(string s)
{
    int n = s.length();
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
 
        // For the existing character in the string
        // the length will be 1
        dp[i][0][s[i - 1] - 'a'] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < 26; k++) {
 
                // The ith character of the string
                // is equal to kth
                if (s[i - 1] == char(k + 'a'))
                    dp[i][j][k] = dp[i - 1][j][k] + 1;
                else if (j != 0)
 
                    // The ith character is not equal to
                    // kth, j != 0 as for j = 0
                    // we have done previously
                    dp[i][j][k] = dp[i - 1][j - 1][k] + 1;
            }
        }
    }
 
    // The ans array which stores length of
    // longest substring for any character
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            for (int k = 1; k <= n; k++)
 
                // Maximum among all indices
                ans[i][j] = max(ans[i][j], dp[k][i][j]);
        }
    }
}
 
// Function to find the longest substrings
vector<int> query(string s,
                  vector<pair<int, char> >& queries)
{
    preprocess(s);
    vector<int> res;
    for (auto u : queries) {
        res.push_back(ans[u.first][u.second - 'a']);
    }
    return res;
}
 
// Driver code
int main()
{
    string s = "yamatonadeshiko";
    vector<pair<int, char> > queries;
    queries.push_back({ 1, 'a' });
    queries.push_back({ 2, 'a' });
    queries.push_back({ 3, 'a' });
    queries.push_back({ 4, 'a' });
    queries.push_back({ 5, 'a' });
    queries.push_back({ 1, 'b' });
    queries.push_back({ 2, 'b' });
    queries.push_back({ 3, 'b' });
    queries.push_back({ 4, 'b' });
    queries.push_back({ 5, 'b' });
 
    // Function call
    vector<int> sol = query(s, queries);
    for (int x : sol)
        cout << x << " ";
    return 0;
}

// Java code of above mentioned approach
import java.io.*;
import java.util.*;
 
class Pair {
    int first;
    char second;
    Pair(int fi, char sec)
    {
        first = fi;
        second = sec;
    }
}
class GFG {
    static int dp[][][] = new int[1001][1001][26];
    static int ans[][] = new int[1001][26];
 
    // Precomputation to get the values
    // of the function f() and g()
    public static void preprocess(String s)
    {
        int n = s.length();
        for (int i = 1; i <= n; i++) {
 
            // For the existing character in the string
            // the length will be 1
            dp[i][0][s.charAt(i - 1) - 'a'] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k < 26; k++) {
 
                    // The ith character of the string
                    // is equal to kth
                    if (s.charAt(i - 1) == (char)(k + 'a'))
                        dp[i][j][k] = dp[i - 1][j][k] + 1;
                    else if (j != 0)
 
                        // The ith character is not equal to
                        // kth, j != 0 as for j = 0
                        // we have done previously
                        dp[i][j][k]
                            = dp[i - 1][j - 1][k] + 1;
                }
            }
        }
 
        // The ans array which stores length of
        // longest substring for any character
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                for (int k = 1; k <= n; k++)
 
                    // Maximum among all indices
                    ans[i][j]
                        = Math.max(ans[i][j], dp[k][i][j]);
            }
        }
    }
 
    // Function to find the longest substrings
    public static ArrayList<Integer> query(String s,
                                           Pair queries[])
    {
        preprocess(s);
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < queries.length; i++) {
            res.add(ans[queries[i].first]
                       [queries[i].second - 'a']);
        }
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String s = "yamatonadeshiko";
        Pair queries[]
            = { new Pair(1, 'a'), new Pair(2, 'a'),
                new Pair(3, 'a'), new Pair(4, 'a'),
                new Pair(5, 'a'), new Pair(1, 'b'),
                new Pair(2, 'b'), new Pair(3, 'b'),
                new Pair(4, 'b'), new Pair(5, 'b') };
 
        // Function call
        ArrayList<Integer> sol = query(s, queries);
        for (Integer x : sol)
            System.out.print(x + " ");
    }
}
 
// This code is contributed by Rohit Pradhan

<script>
    // JavaScript code of above mentioned approach
 
 
    let dp = new Array(1001).fill(0).map(() => new Array(1001).fill(0).map(() => new Array(26).fill(0)));
    let ans = new Array(1001).fill(0).map(() => new Array(26).fill(0));
 
    // Precomputation to get the values
    // of the function f() and g()
    const preprocess = (s) => {
        let n = s.length;
        for (let i = 1; i <= n; i++) {
 
            // For the existing character in the string
            // the length will be 1
            dp[i][0][s.charCodeAt(i - 1) - 'a'.charCodeAt(0)] = 1;
        }
        for (let i = 1; i <= n; i++) {
            for (let j = 0; j <= i; j++) {
                for (let k = 0; k < 26; k++) {
 
                    // The ith character of the string
                    // is equal to kth
                    if (s[i - 1] == String.fromCharCode(k + 'a'.charCodeAt(0)))
                        dp[i][j][k] = dp[i - 1][j][k] + 1;
                    else if (j != 0)
 
                        // The ith character is not equal to
                        // kth, j != 0 as for j = 0
                        // we have done previously
                        dp[i][j][k] = dp[i - 1][j - 1][k] + 1;
                }
            }
        }
 
        // The ans array which stores length of
        // longest substring for any character
 
        for (let i = 1; i <= n; i++) {
            for (let j = 0; j < 26; j++) {
                for (let k = 1; k <= n; k++)
 
                    // Maximum among all indices
                    ans[i][j] = Math.max(ans[i][j], dp[k][i][j]);
            }
        }
    }
 
    // Function to find the longest substrings
    const query = (s, queries) => {
        preprocess(s);
        let res = [];
        for (let u in queries) {
            res.push(ans[queries[u][0]][queries[u][1].charCodeAt(0) - 'a'.charCodeAt(0)]);
        }
        return res;
    }
 
    // Driver code
 
    let s = "yamatonadeshiko";
    let queries = [];
    queries.push([1, 'a']);
    queries.push([2, 'a']);
    queries.push([3, 'a']);
    queries.push([4, 'a']);
    queries.push([5, 'a']);
    queries.push([1, 'b']);
    queries.push([2, 'b']);
    queries.push([3, 'b']);
    queries.push([4, 'b']);
    queries.push([5, 'b']);
 
    // Function call
    let sol = query(s, queries);
    for (let x in sol)
        document.write(`${sol[x]} `);
 
    // This code is contributed by rakeshsahni
 
</script>

3 4 5 7 8 1 2 3 4 5 

Complejidad temporal: O(26*N ² + Q)
Espacio auxiliar: O(26*N ² )