La string lexicográficamente más pequeña posible insertando el carácter dado

Dada una string S y un carácter C , la tarea es colocar un carácter en la string de tal manera que la string obtenida sea la string lexicográficamente más pequeña.

Ejemplos:

Entrada: S = “acd”, C = ‘b’
Salida: “abcd”
Explicación: Las posibles strings formadas al colocar el carácter C en una string en diferentes índices son [“bacd”, “abcd”, “acbd”, “acdb ”]
La string lexicográficamente más pequeña obtenida es “abcd”.

Entrada: S = “abcd”, C=’e’
Salida: “abcde”
Explicación: Las posibles strings formadas al colocar el carácter C en una string en diferentes índices son {“eabcd”, “aebcd”, “abecd”, “abced «, «a B C D e»}.
La string lexicográficamente más pequeña es «abcde».

Enfoque: La idea es colocar el carácter justo antes del primer carácter que es lexicográficamente mayor que el carácter C en la string. Si no se encuentra ningún carácter en la string que sea mayor que C , inserte el carácter al final.

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

// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to obtain lexicographically
// smallest string possible by inserting
// character c in the string s
string SmallestString(string s, char c)
{
 
    // Traverse the string
    for (int i = 0; i < s.size(); i++) {
 
        // If the current character is greater
        // than the given character
        if (s[i] > c) {
 
            // Insert the character before
            // the greater character
            s.insert(i, 1, c);
 
            // Return the string
            return s;
        }
    }
 
    // Append the character at the end
    s += c;
 
    // Return the string
    return s;
}
 
// Driver Code
int main()
{
    string S = "acd";
    char C = 'b';
 
    cout << SmallestString(S, C) << endl;
 
    return 0;
}

// Java program to implement the
// above approach
import java.util.*;
 
class GFG{
 
// Function to obtain lexicographically
// smallest String possible by inserting
// character c in the String s
static String SmallestString(String s, char c)
{
     
    // Traverse the String
    for(int i = 0; i < s.length(); i++)
    {
         
        // If the current character is greater
        // than the given character
        if (s.charAt(i) > c)
        {
             
            // Insert the character before
            // the greater character
            String temp = s;
            s = s.substring(0, i);
            s += c;
            s += temp.substring(i, temp.length());
             
            // Return the String
            return s;
        }
    }
     
    // Append the character at the end
    s += c;
     
    // Return the String
    return s;
}
 
// Driver Code
public static void main(String args[])
{
    String S = "acd";
    char C = 'b';
     
    System.out.println(SmallestString(S, C));
}
}
 
// This code is contributed by ipg2016107

# Python3 Program to implement
# the above approach
 
# Function to obtain lexicographically
# smallest string possible by inserting
# character c in the string s
def SmallestString(s, c):
 
    i = 0
 
    # Traverse the string
    while(i < len(s)):
 
      # Check if current character is
      # greater than the given character
        if s[i] > c:
 
            # Insert the character before
            # the first greater character
            s = s[:i] + c + s[i:]
 
            # Return the string
            return s
        i = i + 1
 
    # Append the character at the end
    s = s + c
 
    # Return the string
    return s
 
 
S = 'abd'
C = 'c'
 
# Function call
print(SmallestString(S, C))

// C# program to implement the
// above approach
using System;
 
class GFG{
     
// Function to obtain lexicographically
// smallest String possible by inserting
// character c in the String s
static String SmallestString(String s, char c)
{
     
    // Traverse the String
    for(int i = 0; i < s.Length; i++)
    {
         
        // If the current character is greater
        // than the given character
        if (s[i] > c)
        {
             
            // Insert the character before
            // the greater character
            String temp = s;
            s = s.Substring(0, i);
            s += c;
            s += temp.Substring(i, temp.Length - 1);
             
            // Return the String
            return s;
        }
    }
     
    // Append the character at the end
    s += c;
     
    // Return the String
    return s;
}
 
// Driver Code
public static void Main(String []args)
{
    String S = "acd";
    char C = 'b';
     
    Console.WriteLine(SmallestString(S, C));
}
}
 
// This code is contributed by aashish1995

<script>
// javascript program to implement
// the above approach
 
// Function to obtain lexicographically
// smallest String possible by inserting
// character c in the String s
function SmallestString(s, c)
{
      
    // Traverse the String
    for(let i = 0; i < s.length; i++)
    {
          
        // If the current character is greater
        // than the given character
        if (s[i] > c)
        {
              
            // Insert the character before
            // the greater character
            let temp = s;
            s = s.substring(0, i);
            s += c;
            s += temp.substring(i, temp.length);
              
            // Return the String
            return s;
        }
    }
      
    // Append the character at the end
    s += c;
      
    // Return the String
    return s;
}
 
// Driver code
     let S = "acd";
    let C = 'b';
    document.write(SmallestString(S, C));
      
     // This code is contributed by splevel62.
</script>

abcd

Complejidad de tiempo: O(len(str))
Espacio auxiliar: O(1)