Substring igual más larga con costo menor que K

Dadas dos strings X e Y de la misma longitud, que consisten en letras minúsculas y también un número entero K . La tarea es encontrar la longitud máxima hasta la cual se puede cambiar X a Y dentro del costo K dado . 
El costo de cambiar un carácter viene dado por la diferencia absoluta entre el valor ASCII de los caracteres. Es decir, para cambiar un carácter en el índice i , costo = |x[i] – Y[i]|

Ejemplos: 

Entrada: X = abcd, Y = bcde, K = 3 
Salida: 3 
Explicación: Se pueden cambiar un máximo de 3 caracteres porque el costo de cambiar cada artículo es 1.  

Enfoque: la idea es mantener una array de prefijos de longitud N para almacenar la suma absoluta de las strings. Es decir, el costo de cambiar la string X a Y. Se pueden seguir los siguientes pasos para calcular el resultado: 

• Mantenga dos punteros, digamos i y j .
• En un ciclo while, verifique si la diferencia entre el i ^-ésimo índice y el j ^-ésimo índice de la array de prefijos es mayor que el costo dado o no.
• Si la diferencia es mayor que el costo dado, aumente el indicador j para compensar el costo, de lo contrario, aumente el indicador i.

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

// C++ program to find the
// maximum length of equal substring
// within a given cost
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum length
int solve(string X, string Y, int N, int K)
{
 
    int count[N + 1] = { 0 };
    int sol = 0;
    count[0] = 0;
 
    // Fill the prefix array with
    // the difference of letters
    for (int i = 1; i <= N; i++) {
 
        count[i] = count[i - 1] + abs(X[i - 1] - Y[i - 1]);
    }
 
    int j = 0;
 
    for (int i = 1; i <= N; i++) {
        while ((count[i] - count[j]) > K) {
 
            j++;
        }
 
        // Update the maximum length
        sol = max(sol, i - j);
    }
 
    return sol;
}
 
// Driver code
int main()
{
 
    int N = 4;
 
    string X = "abcd", Y = "bcde";
 
    int K = 3;
 
    cout << solve(X, Y, N, K) << "\n";
 
    return 0;
}

// Java program to find the
// maximum length of equal subString
// within a given cost
class GFG
{
 
// Function to find the maximum length
static int solve(String X, String Y,
                int N, int K)
{
 
    int []count = new int[N + 1];
    int sol = 0;
    count[0] = 0;
 
    // Fill the prefix array with
    // the difference of letters
    for (int i = 1; i <= N; i++)
    {
 
        count[i] = count[i - 1] +
                Math.abs(X.charAt(i - 1) -
                Y.charAt(i - 1));
    }
 
    int j = 0;
 
    for (int i = 1; i <= N; i++)
    {
        while ((count[i] - count[j]) > K)
        {
            j++;
        }
 
        // Update the maximum length
        sol = Math.max(sol, i - j);
    }
 
    return sol;
}
 
// Driver code
public static void main(String[] args)
{
 
    int N = 4;
    String X = "abcd", Y = "bcde";
    int K = 3;
 
    System.out.print(solve(X, Y, N, K) + "\n");
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to find the
# maximum length of equal subString
# within a given cost
 
# Function to find the maximum length
def solve(X, Y, N, K):
    count = [0] * (N + 1);
    sol = 0;
    count[0] = 0;
 
    # Fill the prefix array with
    # the difference of letters
    for i in range(1, N + 1):
        count[i] = (count[i - 1] +
                    abs(ord(X[i - 1]) -
                    ord(Y[i - 1])));
 
    j = 0;
 
    for i in range(1, N + 1):
        while ((count[i] - count[j]) > K):
            j += 1;
 
        # Update the maximum length
        sol = max(sol, i - j);
 
    return sol;
 
# Driver code
if __name__ == '__main__':
    N = 4;
    X = "abcd";
    Y = "bcde";
    K = 3;
 
    print(solve(X, Y, N, K));
 
# This code is contributed by PrinciRaj1992

// C# program to find the
// maximum length of equal subString
// within a given cost
using System;
 
class GFG
{
     
    // Function to find the maximum length
    static int solve(string X, string Y,
                    int N, int K)
    {
     
        int []count = new int[N + 1];
        int sol = 0;
        count[0] = 0;
     
        // Fill the prefix array with
        // the difference of letters
        for (int i = 1; i <= N; i++)
        {
     
            count[i] = count[i - 1] +
                    Math.Abs(X[i - 1] -
                    Y[i - 1]);
        }
     
        int j = 0;
     
        for (int i = 1; i <= N; i++)
        {
            while ((count[i] - count[j]) > K)
            {
                j++;
            }
     
            // Update the maximum length
            sol = Math.Max(sol, i - j);
        }
     
        return sol;
    }
 
    // Driver code
    public static void Main()
    {
     
        int N = 4;
        string X = "abcd", Y = "bcde";
        int K = 3;
     
        Console.WriteLine(solve(X, Y, N, K) + "\n");
    }
}
 
// This code is contributed by AnkitRai01

<script>
    // Javascript program to find the
    // maximum length of equal subString
    // within a given cost
     
    // Function to find the maximum length
    function solve(X, Y, N, K)
    {
       
        let count = new Array(N + 1);
        count.fill(0);
        let sol = 0;
        count[0] = 0;
       
        // Fill the prefix array with
        // the difference of letters
        for (let i = 1; i <= N; i++)
        {
       
            count[i] = count[i - 1] +
                    Math.abs(X[i - 1].charCodeAt() -
                    Y[i - 1].charCodeAt());
        }
       
        let j = 0;
       
        for (let i = 1; i <= N; i++)
        {
            while ((count[i] - count[j]) > K)
            {
                j++;
            }
       
            // Update the maximum length
            sol = Math.max(sol, i - j);
        }
       
        return sol;
    }
     
    let N = 4;
    let X = "abcd", Y = "bcde";
    let K = 3;
 
    document.write(solve(X, Y, N, K));
         
</script>

3