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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por vandanakillari54935 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA