Substring de longitud máxima que tiene todos los mismos caracteres después de k cambia

Tenemos una string de longitud n, que consiste solo en MAYÚSCULAS y MINÚSCULAS y tenemos un número k (siempre menor que n y mayor que 0). Podemos hacer como máximo k cambios en nuestra string de modo que podamos obtener una substring de longitud máxima que tenga todos los mismos caracteres.

Ejemplos: 

n = length of string
k = changes you can make
Input : n = 5 k = 2
        str = ABABA
Output : maximum length = 5
which will be (AAAAA)

Input : n = 6 k = 4
       str = HHHHHH
Output : maximum length=6
which will be(HHHHHH) 

Verificamos cada carácter del alfabeto inglés (tanto mayúsculas como minúsculas uno por uno). Básicamente, estamos buscando la longitud máxima de la substring que puede formar cada carácter y cualquier carácter que forme la substring de longitud máxima, esa longitud será nuestra respuesta.

1. Comprobamos la longitud máxima de la substring que puede formar cada carácter en un conjunto de 52 caracteres (de ‘A’ a ‘Z’ y de ‘a’ a ‘z’).
2. Para hacer esto, recorremos toda la string y cada vez que encontramos un carácter diferente, aumentamos el conteo.
3. Si el conteo se vuelve mayor que k (en el índice de la derecha), nuevamente comenzamos desde el índice 0 y si encontramos un carácter diferente, disminuiremos el conteo.
4. Cuando el recuento sea igual a k (en el índice izquierdo), en ese punto la longitud será índicederecho-índiceizquierdo+1.
5. Repetimos este proceso hasta llegar al final de la string y en ese punto devolveremos la longitud máxima.
6. Hacemos esto para todos los caracteres y finalmente devolvemos la longitud máxima.

Implementación:

// C++ program to find maximum length equal
// character string with k changes
#include <iostream>
using namespace std;
 
// function to find the maximum length of
// substring having character ch
int findLen(string& A, int n, int k, char ch)
{
    int maxlen = 1;
    int cnt = 0;
    int l = 0, r = 0;
     
    // traverse the whole string
    while (r < n) {
     
        /* if character is not same as ch
           increase count */
        if (A[r] != ch)
            ++cnt;
 
        /* While  count > k  traverse the string
           again until count becomes less than k
           and decrease the count when characters
           are not same */
        while (cnt > k) {
            if (A[l] != ch)
                --cnt;
            ++l;
        }
 
        /* length of substring will be rightIndex -
           leftIndex + 1. Compare this with the maximum
           length and return maximum length */
        maxlen = max(maxlen, r - l + 1);
        ++r;
    }
    return maxlen;
}
 
// function which returns maximum length of substring
int answer(string& A, int n, int k)
{
    int maxlen = 1;
    for (int i = 0; i < 26; ++i) {
        maxlen = max(maxlen, findLen(A, n, k, i+'A'));
        maxlen = max(maxlen, findLen(A, n, k, i+'a'));
    }
    return maxlen;
}
 
// Driver code
int main()
{
    int n = 5, k = 2;
    string A = "ABABA";
    cout << "Maximum length = " << answer(A, n, k) << endl;
 
    n = 6, k = 4;
    string B = "HHHHHH";
    cout << "Maximum length = " << answer(B, n, k) << endl;
    return 0;
}

// Java program to find maximum length equal
// character string with k changes
 
public class GFG
{
    // method to find the maximum length of
    // substring having character ch
    static int findLen(String A, int n, int k, char ch)
    {
        int maxlen = 1;
        int cnt = 0;
        int l = 0, r = 0;
          
        // traverse the whole string
        while (r < n) {
          
            /* if character is not same as ch
               increase count */
            if (A.charAt(r) != ch)
                ++cnt;
      
            /* While  count > k  traverse the string
               again until count becomes less than k
               and decrease the count when characters
               are not same */
            while (cnt > k) {
                if (A.charAt(l) != ch)
                    --cnt;
                ++l;
            }
      
            /* length of substring will be rightIndex -
               leftIndex + 1. Compare this with the maximum
               length and return maximum length */
            maxlen = Math.max(maxlen, r - l + 1);
            ++r;
        }
        return maxlen;
    }
      
    // method which returns maximum length of substring
    static int answer(String A, int n, int k)
    {
        int maxlen = 1;
        for (int i = 0; i < 26; ++i) {
            maxlen = Math.max(maxlen, findLen(A, n, k, (char) (i+'A')));
            maxlen = Math.max(maxlen, findLen(A, n, k, (char) (i+'a')));
        }
        return maxlen;
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        int n = 5, k = 2;
        String A = "ABABA";
        System.out.println("Maximum length = " + answer(A, n, k));
      
        n = 6; k = 4;
        String B = "HHHHHH";
        System.out.println("Maximum length = " + answer(B, n, k));
    }
}

# Python3 program to find maximum length
# equal character string with k changes
 
# function to find the maximum length of
# substring having character ch
def findLen(A, n, k, ch):
    maxlen = 1
    cnt = 0
    l = 0
    r = 0
 
    # traverse the whole string
    while r < n:
 
        # if character is not same as ch
        # increase count
        if A[r] != ch:
            cnt += 1
 
        # While count > k traverse the string
        # again until count becomes less than k
        # and decrease the count when characters
        # are not same
        while cnt > k:
            if A[l] != ch:
                cnt -= 1
            l += 1
 
        # length of substring will be rightIndex -
        # leftIndex + 1. Compare this with the
        # maximum length and return maximum length
        maxlen = max(maxlen, r - l + 1)
        r += 1
 
    return maxlen
 
# function which returns
# maximum length of substring
def answer(A, n, k):
    maxlen = 1
    for i in range(26):
        maxlen = max(maxlen, findLen(A, n, k,
                             chr(i + ord('A'))))
        maxlen = max(maxlen, findLen(A, n, k,
                             chr(i + ord('a'))))
 
    return maxlen
 
# Driver Code
if __name__ == "__main__":
    n = 5
    k = 2
    A = "ABABA"
    print("Maximum length =",
             answer(A, n, k))
 
    n = 6
    k = 4
    B = "HHHHHH"
    print("Maximum length =",
             answer(B, n, k))
 
# This code is contributed by
# sanjeev2552

// C# program to find maximum length equal
// character string with k changes
using System;
 
class GFG
{
     
    // method to find the maximum length of
    // substring having character ch
    public static int findLen(string A, int n,
                               int k, char ch)
    {
        int maxlen = 1;
        int cnt = 0;
        int l = 0, r = 0;
 
        // traverse the whole string
        while (r < n)
        {
 
            // if character is
            // not same as ch
            // increase count
            if (A[r] != ch)
            {
                ++cnt;
            }
 
            // While count > k traverse
            // the string again until
            // count becomes less than
            // k and decrease the
            // count when characters
            // are not same
            while (cnt > k)
            {
                if (A[l] != ch)
                {
                    --cnt;
                }
                ++l;
            }
 
            // length of substring
            // will be rightIndex -
            // leftIndex + 1.
            // Compare this with the maximum
            // length and return maximum length
            maxlen = Math.Max(maxlen, r - l + 1);
            ++r;
        }
        return maxlen;
    }
 
    // method which returns
    // maximum length of substring
    public static int answer(string A, int n, int k)
    {
        int maxlen = 1;
        for (int i = 0; i < 26; ++i)
        {
            maxlen = Math.Max(maxlen,
              findLen(A, n, k, (char)(i + 'A')));
               
            maxlen = Math.Max(maxlen,
              findLen(A, n, k, (char)(i + 'a')));
        }
        return maxlen;
    }
 
// Driver Method
public static void Main(string[] args)
{
    int n = 5, k = 2;
    string A = "ABABA";
    Console.WriteLine("Maximum length = "
                      + answer(A, n, k));
 
    n = 6;
    k = 4;
    string B = "HHHHHH";
    Console.WriteLine("Maximum length = "
                      + answer(B, n, k));
}
}
 
// This code is contributed by Shrikant13

<?php
// PHP program to find maximum length equal
// character string with k changes
 
// function to find the maximum length
// of substring having character ch
function findLen($A, $n, $k, $ch)
{
    $maxlen = 1; $cnt = 0;
    $l = 0; $r = 0;
     
    // traverse the whole string
    while ($r < $n)
    {
     
        /* if character is not same as
        ch increase count */
        if ($A[$r] != $ch)
            ++$cnt;
 
        /* While count > k traverse the string
        again until count becomes less than k
        and decrease the count when characters
        are not same */
        while ($cnt > $k)
        {
            if ($A[$l] != $ch)
                --$cnt;
            ++$l;
        }
 
        /* length of substring will be rightIndex -
        leftIndex + 1. Compare this with the maximum
        length and return maximum length */
        $maxlen = max($maxlen, $r - $l + 1);
        ++$r;
    }
    return $maxlen;
}
 
// function which returns maximum
// length of substring
function answer($A, $n, $k)
{
    $maxlen = 1;
    for ($i = 0; $i < 26; ++$i)
    {
        $maxlen = max($maxlen,
                      findLen($A, $n, $k, $i + 'A'));
        $maxlen = max($maxlen,
                      findLen($A, $n, $k, $i + 'a'));
    }
    return $maxlen;
}
 
// Driver code
$n = 5; $k = 2; $A = "ABABA";
echo "Maximum length = " . answer($A, $n, $k) . "\n";
 
$n = 6; $k = 4; $B = "HHHHHH";
echo "Maximum length = " . answer($B, $n, $k) . "\n";
  
// This code is contributed by ita_c
?>

<script>
// Javascript program to find maximum length equal
// character string with k changes
     
    // method to find the maximum length of
    // substring having character ch
    function findLen(A,n,k,ch)
    {
        let maxlen = 1;
        let cnt = 0;
        let l = 0, r = 0;
            
        // traverse the whole string
        while (r < n) {
            
            /* if character is not same as ch
               increase count */
            if (A[r] != ch)
                ++cnt;
        
            /* While  count > k  traverse the string
               again until count becomes less than k
               and decrease the count when characters
               are not same */
            while (cnt > k) {
                if (A[l] != ch)
                    --cnt;
                ++l;
            }
        
            /* length of substring will be rightIndex -
               leftIndex + 1. Compare this with the maximum
               length and return maximum length */
            maxlen = Math.max(maxlen, r - l + 1);
            ++r;
        }
        return maxlen;
    }
     
    // method which returns maximum length of substring
    function answer(A,n,k)
    {
        let maxlen = 1;
        for (let i = 0; i < 26; ++i) {
            maxlen = Math.max(maxlen, findLen(A, n, k, String.fromCharCode(i+'A'.charCodeAt(0))));
            maxlen = Math.max(maxlen, findLen(A, n, k, String.fromCharCode (i+'a'.charCodeAt(0))));
        }
        return maxlen;
    }
     
    // Driver Method
    let  n = 5, k = 2;
    let A = "ABABA";
    document.write("Maximum length = " + answer(A, n, k)+"<br>");
     
    n = 6; k = 4;
    let B = "HHHHHH";
    document.write("Maximum length = " + answer(B, n, k));
     
    //This code is contributed by rag2127
     
</script>

Maximum length = 5
Maximum length = 6

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

Este artículo es una contribución de Niteesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.