La subsecuencia lexicográficamente más pequeña posible eliminando un carácter de una string dada

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++ 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 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 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# 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

<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++ 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 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 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# 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

<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)