Dada una string S de longitud N , la tarea es encontrar la subsecuencia lexicográficamente más pequeña de longitud (N – 1) , es decir, eliminando un solo carácter de la string dada.
Ejemplos:
Entrada: S = “geeksforgeeks”
Salida: “eeksforgeeks”
Explicación: Lexicográficamente, la subsecuencia más pequeña posible es “eeksforgeeks”.Entrada: S = “zxvsjas”
Salida: “xvsjas”
Explicación: Lexicográficamente, la subsecuencia más pequeña posible es “xvsjas”.
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de longitud (N – 1) a partir de la string dada y almacenar todas las subsecuencias en una array . Ahora, ordene la array e imprima la string en la posición 0 para la subsecuencia lexicográficamente más pequeña.
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 lexicographically
// smallest subsequence of length N-1
void firstSubsequence(string s)
{
vector<string> allsubseq;
string k;
// Generate all subsequence of
// length N-1
for (int i = 0; i < s.length(); i++) {
// Store main value of string str
k = s;
// Erasing element at position i
k.erase(i, 1);
allsubseq.push_back(k);
}
// Sort the vector
sort(allsubseq.begin(),
allsubseq.end());
// Print first element of vector
cout << allsubseq[0];
}
// Driver Code
int main()
{
// Given string S
string S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the lexicographically
// smallest subsequence of length N-1
static void firstSubsequence(String s)
{
Vector<String> allsubseq = new Vector<>();
// Generate all subsequence of
// length N-1
for(int i = 0; i < s.length(); i++)
{
String k = "";
// Store main value of String str
for(int j = 0; j < s.length(); j++)
{
if (i != j)
{
k += s.charAt(j);
}
}
allsubseq.add(k);
}
// Sort the vector
Collections.sort(allsubseq);
// Print first element of vector
System.out.print(allsubseq.get(0));
}
// Driver Code
public static void main(String[] args)
{
// Given String S
String S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function to find the lexicographically
# smallest subsequence of length N-1
def firstSubsequence(s):
allsubseq = []
k = []
# Generate all subsequence of
# length N-1
for i in range(len(s)):
# Store main value of string str
k = [i for i in s]
# Erasing element at position i
del k[i]
allsubseq.append("".join(k))
# Sort the vector
allsubseq = sorted(allsubseq)
# Print first element of vector
print(allsubseq[0])
# Driver Code
if __name__ == '__main__':
# Given string S
S = "geeksforgeeks"
# Function Call
firstSubsequence(S)
# 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 lexicographically
// smallest subsequence of length N-1
static void firstSubsequence(string s)
{
List<string> allsubseq = new List<string>();
// Generate all subsequence of
// length N-1
for(int i = 0; i < s.Length; i++)
{
string k = "";
// Store main value of string str
for(int j = 0; j < s.Length; j++)
{
if (i != j)
{
k += s[j];
}
}
allsubseq.Add(k);
}
// Sort the vector
allsubseq.Sort();
// Print first element of vector
Console.WriteLine(allsubseq[0]);
}
// Driver Code
public static void Main()
{
// Given string S
string S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// Function to find the lexicographically
// smallest subsequence of length N-1
function firstSubsequence(s)
{
let allsubseq = [];
// Generate all subsequence of
// length N-1
for(let i = 0; i < s.length; i++)
{
let k = "";
// Store main value of String str
for(let j = 0; j < s.length; j++)
{
if (i != j)
{
k += s[j];
}
}
allsubseq.push(k);
}
// Sort the vector
(allsubseq).sort();
// Print first element of vector
document.write(allsubseq[0]);
}
// Driver Code
// Given String S
let S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
// This code is contributed by patel2127
</script>
Producción:
eeksforgeeks
Complejidad temporal: O(N *N)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es iterar sobre la string y verificar si el i -ésimo carácter es mayor que (i + 1) -ésimo carácter , luego simplemente eliminar el i -ésimo carácter e imprimir la string restante. De lo contrario, elimine el último elemento e imprima la subsecuencia deseada.
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 lexicographically
// smallest subsequence of length N-1
void firstSubsequence(string s)
{
// Store index of character
// to be deleted
int isMax = -1;
// Traverse the string
for (int i = 0;
i < s.length() - 1; i++) {
// If ith character > (i + 1)th
// character then store it
if (s[i] > s[i + 1]) {
isMax = i;
break;
}
}
// If any character found in non
// alphabetical order then remove it
if (isMax >= 0) {
s.erase(isMax, 1);
}
// Otherwise remove last character
else {
s.erase(s.length() - 1, 1);
}
// Print the resultant subsequence
cout << s;
}
// Driver Code
int main()
{
// Given string S
string S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the lexicographically
// smallest subsequence of length N-1
static void firstSubsequence(String s)
{
// Store index of character
// to be deleted
int isMax = -1;
// Traverse the String
for(int i = 0; i < s.length() - 1; i++)
{
// If ith character > (i + 1)th
// character then store it
if (s.charAt(i) > s.charAt(i + 1))
{
isMax = i;
break;
}
}
// If any character found in non
// alphabetical order then remove it
if (isMax >= 0)
{
s = s.substring(0, isMax) +
s.substring(isMax + 1);
// s.rerase(isMax, 1);
}
// Otherwise remove last character
else
{
//s.erase(s.length() - 1, 1);
s = s.substring(0, s.length() - 1);
}
// Print the resultant subsequence
System.out.print(s);
}
// Driver Code
public static void main(String[] args)
{
// Given String S
String S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach # Function to find the lexicographically # smallest subsequence of length N-1 def firstSubsequence(s): # Store index of character # to be deleted isMax = -1 # Traverse the String for i in range(len(s)): # If ith character > (i + 1)th # character then store it if (s[i] > s[i + 1]): isMax = i break # If any character found in non # alphabetical order then remove it if (isMax >= 0): s = s[0 : isMax] + s[isMax + 1 : len(s)] # s.rerase(isMax, 1); # Otherwise remove last character else: # s.erase(s.length() - 1, 1); s = s[0: s.length() - 1] # Print the resultant subsequence print(s) # Driver Code if __name__ == '__main__': # Given String S S = "geeksforgeeks" # Function Call firstSubsequence(S) # This code is contributed by Princi Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the lexicographically
// smallest subsequence of length N-1
static void firstSubsequence(String s)
{
// Store index of character
// to be deleted
int isMax = -1;
// Traverse the String
for(int i = 0; i < s.Length - 1; i++)
{
// If ith character > (i + 1)th
// character then store it
if (s[i] > s[i + 1])
{
isMax = i;
break;
}
}
// If any character found in non
// alphabetical order then remove it
if (isMax >= 0)
{
s = s.Substring(0, isMax) +
s.Substring(isMax + 1);
// s.rerase(isMax, 1);
}
// Otherwise remove last character
else
{
//s.erase(s.Length - 1, 1);
s = s.Substring(0, s.Length - 1);
}
// Print the resultant subsequence
Console.Write(s);
}
// Driver Code
public static void Main(String[] args)
{
// Given String S
String S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find the lexicographically
// smallest subsequence of length N-1
function firstSubsequence(s)
{
// Store index of character
// to be deleted
let isMax = -1;
// Traverse the String
for(let i = 0; i < s.length - 1; i++)
{
// If ith character > (i + 1)th
// character then store it
if (s[i] > s[i + 1])
{
isMax = i;
break;
}
}
// If any character found in non
// alphabetical order then remove it
if (isMax >= 0)
{
s = s.substring(0, isMax) +
s.substring(isMax + 1);
// s.rerase(isMax, 1);
}
// Otherwise remove last character
else
{
//s.erase(s.length() - 1, 1);
s = s.substring(0, s.length - 1);
}
// Print the resultant subsequence
document.write(s);
}
// Driver Code
// Given String S
let S = "geeksforgeeks";
// Function Call
firstSubsequence(S);
// This code is contributed by unknown2108
</script>
Producción:
eeksforgeeks
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por veeresh_rex y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA