Dada una string S de longitud N , la tarea es encontrar la subsecuencia lexicográficamente más pequeña de longitud K de la string S (donde K < N ).
Ejemplos:
Entrada: S = “bbcaab”, K = 3
Salida: “aab”Entrada: S = “aabdaabc”, K = 3
Salida: “aaa”
Enfoque ingenuo: generar todas las subsecuencias posibles todas las subsecuencias Posición 0 Complejidad de
tiempo: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es apilar la estructura de datos para realizar un seguimiento de los caracteres en orden creciente, para obtener la subsecuencia lexicográficamente más pequeña. Siga los pasos a continuación para resolver el problema:
- Inicialice una pila, digamos answer , de modo que en cualquier índice de la string, la pila debe contener la subsecuencia de longitud K más pequeña hasta el índice actual.
- Atraviese la cuerda y realice los siguientes pasos:
- Si la pila está vacía , inserte el carácter actual en la pila .
- De lo contrario, itere hasta que el elemento actual de la string S[i] sea menor que el elemento superior de la pila y siga saliendo de la pila para asegurarse de que el tamaño de la pila sea K como máximo .
- Si el tamaño de la pila es inferior a K después del paso anterior, inserte el carácter actual en la pila.
- Después de completar los pasos anteriores, imprima los caracteres almacenados en la pila en orden inverso para obtener la string de subsecuencia resultante.
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 lexicographically
// smallest subsequence of size K
void smallestSubsequence(string& S, int K)
{
// Length of string
int N = S.size();
// Stores the minimum subsequence
stack<char> answer;
// Traverse the string S
for (int i = 0; i < N; ++i) {
// If the stack is empty
if (answer.empty()) {
answer.push(S[i]);
}
else {
// Iterate till the current
// character is less than the
// the character at the top of stack
while ((!answer.empty())
&& (S[i] < answer.top())
// Check if there are enough
// characters remaining
// to obtain length K
&& (answer.size() - 1 + N - i >= K)) {
answer.pop();
}
// If stack size is < K
if (answer.empty() || answer.size() < K) {
// Push the current
// character into it
answer.push(S[i]);
}
}
}
// Stores the resultant string
string ret;
// Iterate until stack is empty
while (!answer.empty()) {
ret.push_back(answer.top());
answer.pop();
}
// Reverse the string
reverse(ret.begin(), ret.end());
// Print the string
cout << ret;
}
// Driver Code
int main()
{
string S = "aabdaabc";
int K = 3;
smallestSubsequence(S, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find lexicographically
// smallest subsequence of size K
static void smallestSubsequence(char []S, int K)
{
// Length of String
int N = S.length;
// Stores the minimum subsequence
Stack<Character> answer = new Stack<>();
// Traverse the String S
for (int i = 0; i < N; ++i) {
// If the stack is empty
if (answer.isEmpty()) {
answer.add(S[i]);
}
else {
// Iterate till the current
// character is less than the
// the character at the top of stack
while ((!answer.isEmpty())
&& (S[i] < answer.peek())
// Check if there are enough
// characters remaining
// to obtain length K
&& (answer.size() - 1 + N - i >= K)) {
answer.pop();
}
// If stack size is < K
if (answer.isEmpty() || answer.size() < K) {
// Push the current
// character into it
answer.add(S[i]);
}
}
}
// Stores the resultant String
String ret="";
// Iterate until stack is empty
while (!answer.isEmpty()) {
ret+=(answer.peek());
answer.pop();
}
// Reverse the String
ret = reverse(ret);
// Print the String
System.out.print(ret);
}
static String reverse(String input) {
char[] a = input.toCharArray();
int l, r = a.length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.valueOf(a);
}
// Driver Code
public static void main(String[] args)
{
String S = "aabdaabc";
int K = 3;
smallestSubsequence(S.toCharArray(), K);
}
}
// This code is contributed by shikhasingrajput
Python3
# CPP program for the above approach # Function to find lexicographically # smallest subsequence of size K def smallestSubsequence(S, K): # Length of string N = len(S) # Stores the minimum subsequence answer = [] # Traverse the string S for i in range(N): # If the stack is empty if (len(answer) == 0): answer.append(S[i]) else: # Iterate till the current # character is less than the # the character at the top of stack while (len(answer) > 0 and (S[i] < answer[len(answer) - 1]) and (len(answer) - 1 + N - i >= K)): answer = answer[:-1] # If stack size is < K if (len(answer) == 0 or len(answer) < K): # Push the current # character into it answer.append(S[i]) # Stores the resultant string ret = [] # Iterate until stack is empty while (len(answer) > 0): ret.append(answer[len(answer) - 1]) answer = answer[:-1] # Reverse the string ret = ret[::-1] ret = ''.join(ret) # Print the string print(ret) # Driver Code if __name__ == '__main__': S = "aabdaabc" K = 3 smallestSubsequence(S, K) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find lexicographically
// smallest subsequence of size K
static void smallestSubsequence(char []S, int K)
{
// Length of String
int N = S.Length;
// Stores the minimum subsequence
Stack<char> answer = new Stack<char>();
// Traverse the String S
for (int i = 0; i < N; ++i) {
// If the stack is empty
if (answer.Count==0) {
answer.Push(S[i]);
}
else {
// Iterate till the current
// character is less than the
// the character at the top of stack
while ((answer.Count!=0)
&& (S[i] < answer.Peek())
// Check if there are enough
// characters remaining
// to obtain length K
&& (answer.Count - 1 + N - i >= K)) {
answer.Pop();
}
// If stack size is < K
if (answer.Count==0 || answer.Count < K) {
// Push the current
// character into it
answer.Push(S[i]);
}
}
}
// Stores the resultant String
String ret="";
// Iterate until stack is empty
while (answer.Count!=0) {
ret+=(answer.Peek());
answer.Pop();
}
// Reverse the String
ret = reverse(ret);
// Print the String
Console.Write(ret);
}
static String reverse(String input) {
char[] a = input.ToCharArray();
int l, r = a.Length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("",a);
}
// Driver Code
public static void Main(String[] args)
{
String S = "aabdaabc";
int K = 3;
smallestSubsequence(S.ToCharArray(), K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
//Javascript program for the above approach
//function for reverse
function reverse(input) {
a = input;
var l, r = a.length - 1;
for (l = 0; l < r; l++, r--) {
var temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return a;
}
// Function to find lexicographically
// smallest subsequence of size K
function smallestSubsequence(S, K)
{
// Length of string
var N = S.length;
// Stores the minimum subsequence
answer = [];
// Traverse the string S
for (var i = 0; i < N; ++i) {
// If the stack is empty
if (answer.length==0) {
answer.push(S[i]);
}
else {
// Iterate till the current
// character is less than the
// the character at the top of stack
while ((answer.length != 0) && (S[i] < answer[answer.length-1])
// Check if there are enough
// characters remaining
// to obtain length K
&& (answer.length - 1 + N - i >= K)) {
answer.pop();
}
// If stack size is < K
if (answer.length==0 || answer.length < K) {
// Push the current
// character into it
answer.push(S[i]);
}
}
}
// Stores the resultant string
var ret = [];
// Iterate until stack is empty
while (answer.length != 0) {
ret += answer[answer.length -1];
answer.pop();
}
// Reverse the string
reverse(ret);
// Print the string
document.write(ret);
}
var S = "aabdaabc";
var K = 3;
smallestSubsequence(S, K);
// This code is contributed by SoumikMondal
</script>
Producción:
aaa
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA