Dada una string S que consiste en caracteres en minúsculas y un número entero K , la tarea es encontrar la longitud máxima de una subsecuencia que consiste en un solo carácter distinto posible incrementando como máximo K caracteres.
Ejemplos:
Entrada: S = “acscbcca” K = 1
Salida: 5
Explicación: Incrementar el carácter S[4] de ‘b’ a ‘c’, modifica la string a “acscccca”. Por lo tanto, la subsecuencia más larga de los mismos caracteres es “ccccc”. La longitud de la subsecuencia es 5.Entrada: S = “adscassr”, K = 2
Salida: 4
Enfoque: este problema dado se puede resolver utilizando la técnica de ventana deslizante y la clasificación . Siga los pasos para resolver este problema:
- Inicialice las variables, digamos start , end y sum a 0 que almacena los índices inicial y final de las subsecuencias la suma de la ventana deslizante.
- Inicialice una variable, digamos ans a INT_MIN que almacena la longitud de la subsecuencia más larga resultante.
- Ordenar la string dada S .
- Recorra la string sobre el rango [0, N – 1] y realice los siguientes pasos:
- Incrementa el valor de la suma por el valor (S[end] – ‘a’) .
- Iterar un bucle hasta que el valor de (sum + K) sea menor que (S[end] – ‘a’) * (end – start + 1) y realizar los siguientes pasos:
- Decrementa el valor de la suma en ( S[start] – ‘a’) .
- Incrementa el valor del inicio en 1 .
- Después de los pasos anteriores, todos los caracteres sobre el rango [inicio, final] se pueden igualar utilizando como máximo incrementos de K. Por lo tanto, actualice el valor de ans como el máximo de ans y (fin – inicio + 1) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum length
// of a subsequence of same characters
// after at most K increment operations
void maxSubsequenceLen(string S, int K)
{
// Store the size of S
int N = S.length();
int start = 0, end = 0;
// Sort the given string
sort(S.begin(), S.end());
// Stores the maximum length and the
// sum of the sliding window
int ans = INT_MIN, sum = 0;
// Traverse the string S
for (end = 0; end < N; end++) {
// Add the current character
// to the window
sum = sum + (S[end] - 'a');
// Decrease the window size
while (sum + K
< (S[end] - 'a') * (end - start + 1)) {
// Update the value of sum
sum = sum - (S[start] - 'a');
// Increment the value
// of start
start++;
}
// Update the maximum window size
ans = max(ans, end - start + 1);
}
// Print the resultant maximum
// length of the subsequence
cout << ans;
}
// Driver Code
int main()
{
string S = "acscbcca";
int K = 1;
maxSubsequenceLen(S, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.math.*;
import java.util.Arrays;
class GFG{
// Function to find the maximum length
// of a subsequence of same characters
// after at most K increment operations
static void maxSubsequenceLen(String s, int K)
{
// Store the size of s
int N = s.length();
int start = 0, end = 0;
// Sort the given string
//sort(S.begin(), S.end());
// convert input string to char array
char S[] = s.toCharArray();
// sort tempArray
Arrays.sort(S);
// Stores the maximum length and the
// sum of the sliding window
int ans = Integer.MIN_VALUE, sum = 0;
// Traverse the string S
for(end = 0; end < N; end++)
{
// Add the current character
// to the window
sum = sum + (S[end] - 'a');
// Decrease the window size
while (sum + K < (S[end] - 'a') *
(end - start + 1))
{
// Update the value of sum
sum = sum - (S[start] - 'a');
// Increment the value
// of start
start++;
}
// Update the maximum window size
ans = Math.max(ans, end - start + 1);
}
// Print the resultant maximum
// length of the subsequence
System.out.println(ans);
}
// Driver code
public static void main(String args[])
{
String S = "acscbcca";
int K = 1;
maxSubsequenceLen(S, K);
}
}
// This code is contributed by jana_sayantan
Python3
# Python3 program for the above approach
# Function to find the maximum length
# of a subsequence of same characters
# after at most K increment operations
def maxSubsequenceLen(S, K):
# Store the size of S
N = len(S)
start, end = 0, 0
# Sort the given string
S = sorted(S)
# Stores the maximum length and the
# sum of the sliding window
ans, sum =-10**9, 0
# Traverse the S
for end in range(N):
# Add the current character
# to the window
sum = sum + (ord(S[end]) - ord('a'))
# Decrease the window size
while (sum + K < (ord(S[end]) - ord('a')) *
(end - start + 1)):
# Update the value of sum
sum = sum - (ord(S[start]) - ord('a'))
# Increment the value
# of start
start += 1
# Update the maximum window size
ans = max(ans, end - start + 1)
# Print the resultant maximum
# length of the subsequence
print (ans)
# Driver Code
if __name__ == '__main__':
S = "acscbcca"
K = 1
maxSubsequenceLen(S, K)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the maximum length
// of a subsequence of same characters
// after at most K increment operations
static void maxSubsequenceLen(string s, int K)
{
// Store the size of s
int N = s.Length;
int start = 0, end = 0;
// Sort the given string
//sort(S.begin(), S.end());
// convert input string to char array
char[] S= s.ToCharArray();
// sort tempArray
Array.Sort(S);
// Stores the maximum length and the
// sum of the sliding window
int ans = Int32.MinValue, sum = 0;
// Traverse the string S
for(end = 0; end < N; end++)
{
// Add the current character
// to the window
sum = sum + (S[end] - 'a');
// Decrease the window size
while (sum + K < (S[end] - 'a') *
(end - start + 1))
{
// Update the value of sum
sum = sum - (S[start] - 'a');
// Increment the value
// of start
start++;
}
// Update the maximum window size
ans = Math.Max(ans, end - start + 1);
}
// Print the resultant maximum
// length of the subsequence
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
string S = "acscbcca";
int K = 1;
maxSubsequenceLen(S, K);
}
}
// This code is contributed by souravghosh0416.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum length
// of a subsequence of same characters
// after at most K increment operations
function maxSubsequenceLen(s, K)
{
// Store the size of s
var N = s.length;
var start = 0, end = 0;
// Sort the given string
//sort(S.begin(), S.end());
// convert input string to char array
var S = s.split('');
// sort tempArray
S.sort();
// Stores the maximum length and the
// sum of the sliding window
var ans = Number.MIN_VALUE, sum = 0;
// Traverse the string S
for(end = 0; end < N; end++)
{
// Add the current character
// to the window
sum = sum + (S[end].charCodeAt(0) -
'a'.charCodeAt(0));
// Decrease the window size
while (sum + K < (S[end].charCodeAt(0) -
'a'.charCodeAt(0)) *
(end - start + 1))
{
// Update the value of sum
sum = sum - (S[start].charCodeAt(0) -
'a'.charCodeAt(0));
// Increment the value
// of start
start++;
}
// Update the maximum window size
ans = Math.max(ans, end - start + 1);
}
// Print the resultant maximum
// length of the subsequence
document.write(ans);
}
// Driver code
var S = "acscbcca";
var K = 1;
maxSubsequenceLen(S, K);
// This code is contributed by Amit Katiyar
</script>
Producción:
5
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA