Dada una string P que consta de letras minúsculas en inglés y una string de bits de 26 dígitos Q , donde 1 representa el carácter especial y 0 representa un carácter normal para los 26 alfabetos ingleses. La tarea es encontrar la longitud de la substring más larga con como máximo K caracteres normales.
Ejemplos:
Entrada: P = “normal”, Q = “000000000000000000000000000”, K=1
Salida: 1
Explicación: En la string Q todos los caracteres son normales.
Por lo tanto, podemos seleccionar cualquier substring de longitud 1.Entrada: P = “jirafa”, Q = “01111001111111111011111111”, K=2
Salida: 3
Explicación: Los caracteres normales en P desde Q son {a, f, g, r}.
Por lo tanto, las substrings posibles con un máximo de 2 caracteres normales son {gir, ira, ffe}.
La longitud máxima de todas las substrings es 3.
Enfoque:
Para resolver el problema mencionado anteriormente, utilizaremos el concepto de dos punteros. Por lo tanto, mantenga los punteros izquierdo y derecho de la substring y un recuento de caracteres normales. Incremente el índice derecho hasta que el recuento de caracteres normales sea como máximo K. Luego actualice la respuesta con una longitud máxima de substring encontrada hasta ahora. Incremente el índice izquierdo y disminuya el conteo hasta que sea mayor que K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find
// length of longest substring
// with at most K normal characters
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// length of normal substrings
int maxNormalSubstring(string& P, string& Q,
int K, int N)
{
if (K == 0)
return 0;
// keeps count of normal characters
int count = 0;
// indexes of substring
int left = 0, right = 0;
// maintain length of longest substring
// with at most K normal characters
int ans = 0;
while (right < N) {
while (right < N && count <= K) {
// get position of character
int pos = P[right] - 'a';
// check if current character is normal
if (Q[pos] == '0') {
// check if normal characters
// count exceeds K
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with substring length
if (count <= K)
ans = max(ans, right - left);
}
while (left < right) {
// get position of character
int pos = P[left] - 'a';
left++;
// check if character is
// normal then decrement count
if (Q[pos] == '0')
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver code
int main()
{
// initialise the string
string P = "giraffe", Q = "01111001111111111011111111";
int K = 2;
int N = P.length();
cout << maxNormalSubstring(P, Q, K, N);
return 0;
}
Java
// Java implementation to Find
// length of longest subString
// with at most K normal characters
class GFG{
// Function to find maximum
// length of normal subStrings
static int maxNormalSubString(char []P, char []Q,
int K, int N)
{
if (K == 0)
return 0;
// keeps count of normal characters
int count = 0;
// indexes of subString
int left = 0, right = 0;
// maintain length of longest subString
// with at most K normal characters
int ans = 0;
while (right < N) {
while (right < N && count <= K) {
// get position of character
int pos = P[right] - 'a';
// check if current character is normal
if (Q[pos] == '0') {
// check if normal characters
// count exceeds K
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with subString length
if (count <= K)
ans = Math.max(ans, right - left);
}
while (left < right) {
// get position of character
int pos = P[left] - 'a';
left++;
// check if character is
// normal then decrement count
if (Q[pos] == '0')
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
// initialise the String
String P = "giraffe", Q = "01111001111111111011111111";
int K = 2;
int N = P.length();
System.out.print(maxNormalSubString(P.toCharArray(), Q.toCharArray(), K, N));
}
}
// This code is contributed by Princi Singh
Python3
# Function to find maximum
# length of normal substrings
def maxNormalSubstring(P, Q, K, N):
if (K == 0):
return 0
# keeps count of normal characters
count = 0
# indexes of substring
left, right = 0, 0
# maintain length of longest substring
# with at most K normal characters
ans = 0
while (right < N):
while (right < N and count <= K):
# get position of character
pos = ord(P[right]) - ord('a')
# check if current character is normal
if (Q[pos] == '0'):
# check if normal characters
# count exceeds K
if (count + 1 > K):
break
else:
count += 1
right += 1
# update answer with substring length
if (count <= K):
ans = max(ans, right - left)
while (left < right):
# get position of character
pos = ord(P[left]) - ord('a')
left += 1
# check if character is
# normal then decrement count
if (Q[pos] == '0'):
count -= 1
if (count < K):
break
return ans
# Driver code
if(__name__ == "__main__"):
# initialise the string
P = "giraffe"
Q = "01111001111111111011111111"
K = 2
N = len(P)
print(maxNormalSubstring(P, Q, K, N))
# This code is contributed by skylags
C#
// C# implementation to Find
// length of longest subString
// with at most K normal characters
using System;
public class GFG{
// Function to find maximum
// length of normal subStrings
static int maxNormalSubString(char []P, char []Q,
int K, int N)
{
if (K == 0)
return 0;
// keeps count of normal characters
int count = 0;
// indexes of subString
int left = 0, right = 0;
// maintain length of longest subString
// with at most K normal characters
int ans = 0;
while (right < N) {
while (right < N && count <= K) {
// get position of character
int pos = P[right] - 'a';
// check if current character is normal
if (Q[pos] == '0') {
// check if normal characters
// count exceeds K
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with subString length
if (count <= K)
ans = Math.Max(ans, right - left);
}
while (left < right) {
// get position of character
int pos = P[left] - 'a';
left++;
// check if character is
// normal then decrement count
if (Q[pos] == '0')
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
// initialise the String
String P = "giraffe", Q = "01111001111111111011111111";
int K = 2;
int N = P.Length;
Console.Write(maxNormalSubString(P.ToCharArray(),
Q.ToCharArray(), K, N));
}
}
// This code contributed by Princi Singh
Javascript
<script>
// Javascript implementation to Find
// length of longest substring
// with at most K normal character
// Function to find maximum
// length of normal substrings
function maxNormalSubstring(P, Q, K, N)
{
if (K == 0)
return 0;
// keeps count of normal characters
var count = 0;
// indexes of substring
var left = 0, right = 0;
// maintain length of longest substring
// with at most K normal characters
var ans = 0;
while (right < N) {
while (right < N && count <= K) {
// get position of character
var pos = P[right].charCodeAt(0) - 'a'.charCodeAt(0);
// check if current character is normal
if (Q[pos] == '0') {
// check if normal characters
// count exceeds K
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with substring length
if (count <= K)
ans = Math.max(ans, right - left);
}
while (left < right) {
// get position of character
var pos = P[left].charCodeAt(0) - 'a'.charCodeAt(0);
left++;
// check if character is
// normal then decrement count
if (Q[pos] == '0')
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver code
// initialise the string
var P = "giraffe", Q = "01111001111111111011111111";
var K = 2;
var N = P.length;
document.write( maxNormalSubstring(P, Q, K, N));
</script>
3
Complejidad de tiempo: el método anterior toma tiempo O (N).
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA