Dada una string S y un entero K , la tarea es generar lexicográficamente la string más grande posible a partir de la string dada, eliminando también caracteres, que consta de como máximo K caracteres similares consecutivos.
Ejemplos:
Entrada: S = “baccc”, K = 2
Salida: ccbcaEntrada: S = “ccbbb”, K = 2
Salida: ccbb
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array charset[] para almacenar la frecuencia de cada carácter en la string .
- Recorra la string y almacene la frecuencia de cada carácter en la array.
- Inicialice una cuenta variable para almacenar la cuenta de caracteres consecutivos similares
- Inicialice una string newString para almacenar la string resultante.
- Recorra la array charset[] y añada (i +’a’) a newString .
- Disminuye charset[i] y aumenta el conteo .
- Verifique si count = K y charset[i] > 0 , luego busque el carácter más pequeño más cercano disponible en charset[] y agréguelo a newString . Si el carácter más pequeño más cercano no está disponible, imprima newString
- De lo contrario, restablezca el conteo a 0 .
- Repita los pasos del 2 al 5 hasta que charset[i] > 0
- Finalmente, devuelva newString .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return nearest
// lower character
char nextAvailableChar(vector<int> charset,
int start)
{
// Traverse charset from start-1
for (int i = start - 1; i >= 0; i--)
{
if (charset[i] > 0)
{
charset[i]--;
return char(i + 'a');
}
}
// If no character can be
// appended
return '\0';
}
// Function to find largest string
string newString(string originalLabel,
int limit)
{
int n = originalLabel.length();
// Stores the frequency of
// characters
vector<int> charset(26, 0);
string newStrings = "";
for(char i : originalLabel)
charset[i - 'a']++;
// Traverse the string
for (int i = 25; i >= 0; i--)
{
int count = 0;
// Append larger character
while (charset[i] > 0)
{
newStrings += char(i + 'a');
// Decrease count in charset
charset[i]--;
// Increase count
count++;
// Check if count reached
// to charLimit
if (charset[i] > 0 &&
count == limit)
{
// Find nearest lower char
char next = nextAvailableChar(charset, i);
// If no character can be
// appended
if (next == '\0')
return newStrings;
// Append nearest lower
// character
newStrings += next;
// Reset count for next
// calculation
count = 0;
}
}
}
// Return new largest string
return newStrings;
}
//Driver code
int main()
{
//Given string s
string S = "ccbbb";
int K = 2;
cout << (newString(S, K));
}
// This code is contributed by Mohit Kumar 29
Java
// Java solution for above approach
import java.util.*;
class GFG {
// Function to find largest string
static String newString(String originalLabel,
int limit)
{
int n = originalLabel.length();
// Stores the frequency of characters
int[] charset = new int[26];
// Traverse the string
for (int i = 0; i < n; i++) {
charset[originalLabel.charAt(i) - 'a']++;
}
// Stores the resultant string
StringBuilder newString
= new StringBuilder(n);
for (int i = 25; i >= 0; i--) {
int count = 0;
// Append larger character
while (charset[i] > 0) {
newString.append((char)(i + 'a'));
// Decrease count in charset
charset[i]--;
// Increase count
count++;
// Check if count reached to charLimit
if (charset[i] > 0 && count == limit) {
// Find nearest lower char
Character next
= nextAvailableChar(charset, i);
// If no character can be appended
if (next == null)
return newString.toString();
// Append nearest lower character
newString.append(next);
// Reset count for next calculation
count = 0;
}
}
}
// Return new largest string
return newString.toString();
}
// Function to return nearest lower character
static Character nextAvailableChar(int[] charset,
int start)
{
// Traverse charset from start-1
for (int i = start - 1; i >= 0; i--) {
if (charset[i] > 0) {
charset[i]--;
return (char)(i + 'a');
}
}
// If no character can be appended
return null;
}
// Driver Code
public static void main(String[] args)
{
String S = "ccbbb";
int K = 2;
System.out.println(newString(S, K));
}
}
Python3
# Python3 program for the
# above approach
# Function to return nearest
# lower character
def nextAvailableChar(charset,
start):
# Traverse charset from start-1
for i in range(start - 1,
-1, -1):
if (charset[i] > 0):
charset[i] -= 1
return chr(i + ord('a'))
# If no character can be
# appended
return '\0'
# Function to find largest
# string
def newString(originalLabel,
limit):
n = len(originalLabel)
# Stores the frequency of
# characters
charset = [0] * (26)
newStrings = ""
for i in originalLabel:
charset[ord(i) -
ord('a')] += 1
# Traverse the string
for i in range(25, -1, -1):
count = 0
# Append larger character
while (charset[i] > 0):
newStrings += chr(i + ord('a'))
# Decrease count in
# charset
charset[i] -= 1
# Increase count
count += 1
# Check if count reached
# to charLimit
if (charset[i] > 0 and
count == limit):
# Find nearest lower char
next = nextAvailableChar(charset, i)
# If no character can be
# appended
if (next == '\0'):
return newStrings
# Append nearest lower
# character
newStrings += next
# Reset count for next
# calculation
count = 0
# Return new largest string
return newStrings
# Driver code
if __name__ == "__main__":
# Given string s
S = "ccbbb"
K = 2
print(newString(S, K))
# This code is contributed by Chitranayal
C#
// C# solution for above
// approach
using System;
using System.Text;
class GFG{
// Function to find largest string
static String newString(String originalLabel,
int limit)
{
int n = originalLabel.Length;
// Stores the frequency of
// characters
int[] charset = new int[26];
// Traverse the string
for (int i = 0; i < n; i++)
{
charset[originalLabel[i] - 'a']++;
}
// Stores the resultant string
StringBuilder newString =
new StringBuilder(n);
for (int i = 25; i >= 0; i--)
{
int count = 0;
// Append larger character
while (charset[i] > 0)
{
newString.Append((char)(i + 'a'));
// Decrease count in charset
charset[i]--;
// Increase count
count++;
// Check if count reached
// to charLimit
if (charset[i] > 0 &&
count == limit)
{
// Find nearest lower char
char next =
nextAvailableChar(charset, i);
// If no character can be
// appended
if (next == 0)
return newString.ToString();
// Append nearest lower
// character
newString.Append(next);
// Reset count for next
// calculation
count = 0;
}
}
}
// Return new largest string
return newString.ToString();
}
// Function to return nearest
// lower character
static char nextAvailableChar(int[] charset,
int start)
{
// Traverse charset from start-1
for (int i = start - 1; i >= 0; i--)
{
if (charset[i] > 0)
{
charset[i]--;
return (char)(i + 'a');
}
}
// If no character can
// be appended
return '\0';
}
// Driver Code
public static void Main(String[] args)
{
String S = "ccbbb";
int K = 2;
Console.WriteLine(
newString(S, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript solution for above approach
// Function to find largest string
function newString(originalLabel,limit)
{
let n = originalLabel.length;
// Stores the frequency of characters
let charset = new Array(26);
for(let i = 0; i < 26; i++)
{
charset[i] = 0;
}
// Traverse the string
for (let i = 0; i < n; i++) {
charset[originalLabel[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
// Stores the resultant string
let newString = [];
for (let i = 25; i >= 0; i--) {
let count = 0;
// Append larger character
while (charset[i] > 0) {
newString.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
// Decrease count in charset
charset[i]--;
// Increase count
count++;
// Check if count reached to charLimit
if (charset[i] > 0 && count == limit) {
// Find nearest lower char
let next
= nextAvailableChar(charset, i);
// If no character can be appended
if (next == null)
return newString.join("");
// Append nearest lower character
newString.push(next);
// Reset count for next calculation
count = 0;
}
}
}
// Return new largest string
return newString.join("");
}
// Function to return nearest lower character
function nextAvailableChar(charset,start)
{
// Traverse charset from start-1
for (let i = start - 1; i >= 0; i--) {
if (charset[i] > 0) {
charset[i]--;
return String.fromCharCode(i + 'a'.charCodeAt(0));
}
}
// If no character can be appended
return null;
}
// Driver Code
let S = "ccbbb";
let K = 2;
document.write(newString(S, K));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
ccbb
Complejidad de tiempo: O(N), donde N es la longitud de la string dada
Espacio auxiliar: O(1)