String lexicográficamente más pequeña formada al eliminar como máximo un carácter

Dada una string str , la tarea es encontrar la string lexicográficamente más pequeña que se puede formar eliminando como máximo un carácter de la string dada. 

Ejemplos: 

Input: str = "abcda"  
Output: abca
One can remove 'd' to get "abca" which is 
the lexicographically smallest string possible. 

Input: str = "aaa' 
Output: aa

Enfoque : recorra la string y elimine el i-ésimo carácter en el primer punto donde s[i]>s[i+1] . Si en caso de que no exista tal carácter, elimine el último carácter de la string. 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find the lexicographically
// smallest string by removing at most one character
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the smallest string
string smallest(string s)
{
    int l = s.length();
    string ans = "";
 
    // iterate the string
    for (int i = 0; i < l-1; i++) {
 
        // first point where s[i]>s[i+1]
        if (s[i] > s[i + 1]) {
 
            // append the string without
            // i-th character in it
            for (int j = 0; j < l; j++) {
                if (i != j)
                    ans += s[j];
            }
            return ans;
        }
    }
 
    // leave the last character
    ans = s.substr(0., l - 1);
    return ans;
}
 
// Driver Code
int main()
{
    string s = "abcda";
 
    cout << smallest(s);
 
    return 0;
}

// Java program to find the lexicographically
// smallest String by removing at most one character
 
class GFG {
 
// Function to return the smallest String
    static String smallest(String s) {
        int l = s.length();
        String ans = "";
 
        // iterate the String
        for (int i = 0; i < l-1; i++) {
 
            // first point where s[i]>s[i+1]
            if (s.charAt(i) > s.charAt(i + 1)) {
 
                // append the String without
                // i-th character in it
                for (int j = 0; j < l; j++) {
                    if (i != j) {
                        ans += s.charAt(j);
                    }
                }
                return ans;
            }
        }
 
        // leave the last character
        ans = s.substring(0, l - 1);
        return ans;
    }
 
// Driver Code
    public static void main(String[] args) {
 
        String s = "abcda";
        System.out.println(smallest(s));
    }
}
/* This code is contributed by 29AjayKumar*/

# Python3 program to find the lexicographically
# smallest string by removing at most one character
 
# Function to return the smallest string
def smallest(s):
 
    l = len(s)
    ans = ""
 
    # iterate the string
    for i in range (l-1):
 
        # first point where s[i]>s[i+1]
        if (s[i] > s[i + 1]):
 
            # append the string without
            # i-th character in it
            for j in range (l):
                if (i != j):
                    ans += s[j]
             
            return ans
 
    # leave the last character
    ans = s[0: l - 1]
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    s = "abcda"
 
    print (smallest(s))
 
# This code is contributed by ita_c

// C# program to find the lexicographically
// smallest String by removing at most
// one character
using System;
 
class GFG
{
 
// Function to return the
// smallest String
static String smallest(String s)
{
    int l = s.Length;
    String ans = "";
 
    // iterate the String
    for (int i = 0; i < l-1; i++)
    {
 
        // first point where s[i]>s[i+1]
        if (s[i] > s[i + 1])
        {
 
            // append the String without
            // i-th character in it
            for (int j = 0; j < l; j++)
            {
                if (i != j)
                {
                    ans += s[j];
                }
            }
            return ans;
        }
    }
 
    // leave the last character
    ans = s.Substring(0, l - 1);
    return ans;
}
 
// Driver Code
public static void Main()
{
    String s = "abcda";
    Console.Write(smallest(s));
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program to find the lexicographically
// smallest String by removing at most one character
     
    // Function to return the smallest String
    function smallest(s)
    {
        let l = s.length;
        let ans = "";
  
        // iterate the String
        for (let i = 0; i < l-1; i++)
        {
  
            // first point where s[i]>s[i+1]
            if (s[i] > s[i+1]) {
  
                // append the String without
                // i-th character in it
                for (let j = 0; j < l; j++) {
                    if (i != j) {
                        ans += s[j];
                    }
                }
                return ans;
            }
        }
  
        // leave the last character
        ans = s.substring(0, l - 1);
        return ans;
    }
     
    // Driver Code
    let s = "abcda";
    document.write(smallest(s));
 
// This code is contributed by rag2127
</script>

abca

Complejidad temporal: O(n*n) donde n es la longitud de la string

Espacio auxiliar: O(n) ya que estamos almacenando la respuesta en forma de string.