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.
- 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’).
- Para hacer esto, recorremos toda la string y cada vez que encontramos un carácter diferente, aumentamos el conteo.
- 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.
- Cuando el recuento sea igual a k (en el índice izquierdo), en ese punto la longitud será índicederecho-índiceizquierdo+1.
- Repetimos este proceso hasta llegar al final de la string y en ese punto devolveremos la longitud máxima.
- Hacemos esto para todos los caracteres y finalmente devolvemos la longitud máxima.
Implementación:
C++
// 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
// 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
# 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#
// 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 // 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 ?>
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA