Dada una string S , un entero K y un conjunto de caracteres Q[] , la tarea es encontrar la substring más larga en la string S que contiene como máximo K caracteres del conjunto de caracteres Q[] dado .
Ejemplos:
Entrada: S = “normal”, Q = {“a”, “o”, “n”, “b”, “r”, “l”}, K = 1
Salida: 1
Explicación:
Todos los caracteres en el dado string S están presentes en la array.
Por lo tanto, podemos seleccionar cualquier substring de longitud 1.
Entrada: S = “jirafa”, Q = {“a”, “f”, “g”, “r”}, K = 2
Salida: 3
Explicación:
Posibles substrings con como máximo 2 caracteres
Del conjunto dado son {“gir”, “ira”, “ffe”}
La longitud máxima de todas las substrings es 3.
Enfoque: la idea es usar el concepto de dos punteros para considerar las substrings de longitud máxima, de modo que contenga como máximo K caracteres del conjunto dado. A continuación se muestra la ilustración del enfoque:
- Mantenga dos punteros izquierdo y derecho como 0, para considerar la string entre estos punteros.
- Incremente el puntero derecho hasta que los caracteres del conjunto dado sean como máximo K.
- Actualice la substring de longitud más larga para que sea la diferencia entre el puntero derecho y el puntero izquierdo.
cur_max = max(cur_max, right - left)
- Incremente el puntero izquierdo y si el carácter que se movió fuera de los dos punteros es el carácter del conjunto dado, entonces disminuya la cuenta de los caracteres del conjunto en 1.
- Del mismo modo, repita los pasos anteriores hasta que el puntero derecho no sea igual a la longitud de la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// longest substring in the string
// which contains atmost K characters
// from the given set of characters
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest
// substring in the string
// which contains atmost K characters
// from the given set of characters
int maxNormalSubstring(string& P,
set<char> Q, int K, int N)
{
// Base Condition
if (K == 0)
return 0;
// Count for Characters
// from set in substring
int count = 0;
// Two pointers
int left = 0, right = 0;
int ans = 0;
// Loop to iterate until
// right pointer is not
// equal to N
while (right < N) {
// Loop to increase the substring
// length until the characters from
// set are at most K
while (right < N && count <= K) {
// Check if current pointer
// points a character from set
if (Q.find(P[right]) != Q.end()){
// If the count of the
// char is exceeding the limit
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with
// substring length
if (count <= K)
ans = max(ans, right - left);
}
// Increment the left pointer until
// the count is less than or equal to K
while (left < right) {
left++;
// If the character which comes out is normal character
// then decrement the count by 1
if (Q.find(P[left-1]) != Q.end())
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver Code
int main()
{
string P = "giraffe";
set<char> Q;
// Construction of set
Q.insert('a');
Q.insert('f');
Q.insert('g');
Q.insert('r');
int K = 2;
int N = P.length();
// output result
cout << maxNormalSubstring(P, Q, K, N);
return 0;
}
Java
// Java implementation to find the
// longest substring in the string
// which contains atmost K characters
// from the given set of characters
import java.util.*;
class GFG{
// Function to find the longest
// substring in the string
// which contains atmost K characters
// from the given set of characters
static int maxNormalSubstring(String P,
Set<Character> Q,
int K, int N)
{
// Base Condition
if (K == 0)
return 0;
// Count for Characters
// from set in substring
int count = 0;
// Two pointers
int left = 0, right = 0;
int ans = 0;
// Loop to iterate until
// right pointer is not
// equal to N
while (right < N)
{
// Loop to increase the substring
// length until the characters from
// set are at most K
while (right < N && count <= K)
{
// Check if current pointer
// points a character from set
if (Q.contains(P.charAt(right)))
{
// If the count of the
// char is exceeding the limit
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with
// substring length
if (count <= K)
ans = Math.max(ans, right - left);
}
// Increment the left pointer until
// the count is less than or equal to K
while (left < right)
{
left++;
// If the character which comes out
// then decrement the count by 1
if (Q.contains(P.charAt(left-1)))
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
String P = "giraffe";
Set<Character> Q = new HashSet<>();
// Construction of set
Q.add('a');
Q.add('f');
Q.add('g');
Q.add('r');
int K = 2;
int N = P.length();
// Output result
System.out.println(maxNormalSubstring(P, Q,
K, N));
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to find the
# longest substring in the string
# which contains atmost K characters
# from the given set of characters
# Function to find the longest
# substring in the string
# which contains atmost K characters
# from the given set of characters
def maxNormalSubstring(P, Q, K, N):
# Base Condition
if (K == 0):
return 0
# Count for Characters
# from set in substring
count = 0
# Two pointers
left = 0
right = 0
ans = 0
# Loop to iterate until
# right pointer is not
# equal to N
while (right < N):
# Loop to increase the substring
# length until the characters from
# set are at most K
while (right < N and count <= K):
# Check if current pointer
# points a character from set
if (P[right] in Q):
# If the count of the
# char is exceeding the limit
if (count + 1 > K):
break
else:
count += 1
right += 1
# update answer with
# substring length
if (count <= K):
ans = max(ans, right - left)
# Increment the left pointer until
# the count is less than or equal to K
while (left < right):
left += 1
# If the character which comes out
# then decrement the count by 1
if (P[left-1] in Q):
count -= 1
if (count < K):
break
return ans
# Driver Code
P = "giraffe"
Q = {chr}
# Construction of set
Q.add('a')
Q.add('f')
Q.add('g')
Q.add('r')
K = 2
N = len(P)
# Output result
print(maxNormalSubstring(P, Q, K, N))
# This code is contributed by Sanjit_Prasad
Javascript
<script>
// JavaScript implementation of above approach
// Function to find the longest
// substring in the string
// which contains atmost K characters
// from the given set of characters
function maxNormalSubstring(P, Q, K, N)
{
// Base Condition
if (K == 0)
return 0;
// Count for Characters
// from set in substring
let count = 0;
// Two pointers
let left = 0, right = 0;
let ans = 0;
// Loop to iterate until
// right pointer is not
// equal to N
while (right < N) {
// Loop to increase the substring
// length until the characters from
// set are at most K
while (right < N && count <= K) {
// Check if current pointer
// points a character from set
if (Q.has(P[right])){
// If the count of the
// char is exceeding the limit
if (count + 1 > K)
break;
else
count++;
}
right++;
// update answer with
// substring length
if (count <= K)
ans = Math.max(ans, right - left);
}
// Increment the left pointer until
// the count is less than or equal to K
while (left < right) {
left++;
// If the character which comes out is normal character
// then decrement the count by 1
if (Q.has(P[left-1]))
count--;
if (count < K)
break;
}
}
return ans;
}
// Driver Code
let P = "giraffe"
let Q = new Set()
// Construction of set
Q.add('a')
Q.add('f')
Q.add('g')
Q.add('r')
let K = 2;
let N = P.length;
// output result
document.write(maxNormalSubstring(P, Q, K, N),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
3
Análisis de rendimiento:
- Complejidad de tiempo: O(N)
- Espacio Auxiliar: O(1)
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