Dada una string str de N caracteres, la tarea es encontrar la string lexicográficamente más pequeña que se pueda formar concatenando cualquier prefijo y su forma reflejada.
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: geeeeg
Explicación: La string lexicográficamente más pequeña se puede formar con el prefijo “gee” como “gee” + “eeg”.Entrada: str = “abcd”
Salida: aa
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es elegir el prefijo más grande que tenga sus valores ASCII en orden decreciente. Por lo tanto, recorra la string str y almacene el prefijo más grande que tenga el valor de sus caracteres ASCII en orden decreciente en un prefijo de string . La concatenación de prefijo con su reverso es la respuesta requerida.
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 lexicographically
// smallest string formed by concatenating
// any prefix and its mirrored form
string lexicographicallySmallest(string str)
{
// Stores the largest prefix
// with character in decreasing
// order of ascii value
string prefix = "";
// Initialize prefix string
prefix += str[0];
// Loop to traverse the string
for (int i = 1; i < str.length(); i++) {
// If current character is
// in decreasing order
if (str[i] < prefix.back()) {
prefix += str[i];
}
else if (str[i] == prefix.back()
&& prefix.size() > 1) {
prefix += str[i];
}
else {
break;
}
}
// Stores the reversed prefix string
string rev = prefix;
reverse(rev.begin(), rev.end());
// Return Answer
return prefix + rev;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
cout << lexicographicallySmallest(str);
return 0;
}
Java
// Java program for the above approach
class GFG
{
static String reverse(String str) {
char[] chars = str.toCharArray();
for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
return new String(chars);
}
// Function to find lexicographically
// smallest string formed by concatenating
// any prefix and its mirrored form
static String lexicographicallySmallest(String str)
{
// Stores the largest prefix
// with character in decreasing
// order of ascii value
String prefix = "";
// Initialize prefix string
prefix += str.charAt(0);
// Loop to traverse the string
for (int i = 1; i < str.length(); i++) {
// If current character is
// in decreasing order
if (str.charAt(i) < prefix.charAt(prefix.length() - 1)) {
prefix += str.charAt(i);
}
else if (str.charAt(i) == prefix.charAt(prefix.length() - 1) && prefix.length() > 1) {
prefix += str.charAt(i);
}
else {
break;
}
}
// Stores the reversed prefix string
String rev = reverse(prefix);
// Return Answer
return prefix + rev;
}
// Driver code
public static void main(String args[])
{
String str = "geeksforgeeks";
System.out.println(lexicographicallySmallest(str));
}
}
// This code is contributed by gfgking
Python3
# Python 3 program for the above approach # Function to find lexicographically # smallest string formed by concatenating # any prefix and its mirrored form def lexicographicallySmallest(st): # Stores the largest prefix # with character in decreasing # order of ascii value prefix = "" # Initialize prefix string prefix += st[0] # Loop to traverse the string for i in range(1, len(st)): # If current character is # in decreasing order if (st[i] < prefix[len(prefix)-1]): prefix += st[i] elif (st[i] == prefix[len(prefix)-1] and len(prefix) > 1): prefix += st[i] else: break # Stores the reversed prefix string rev = prefix rev = list(rev) rev.reverse() rev = ''.join(rev) # Return Answer return prefix + rev # Driver code if __name__ == "__main__": st = "geeksforgeeks" print(lexicographicallySmallest(st)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG
{
static string reverse(string str) {
char[] chars = str.ToCharArray();
for (int i = 0, j = str.Length - 1; i < j; i++, j--) {
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
return new string(chars);
}
// Function to find lexicographically
// smallest string formed by concatenating
// any prefix and its mirrored form
static string lexicographicallySmallest(string str)
{
// Stores the largest prefix
// with character in decreasing
// order of ascii value
string prefix = "";
// Initialize prefix string
prefix += str[0];
// Loop to traverse the string
for (int i = 1; i < str.Length; i++) {
// If current character is
// in decreasing order
if (str[i] < prefix[prefix.Length - 1]) {
prefix += str[i];
}
else if (str[i] == prefix[prefix.Length - 1]
&& prefix.Length > 1) {
prefix += str[i];
}
else {
break;
}
}
// Stores the reversed prefix string
string rev = reverse(prefix);
// Return Answer
return prefix + rev;
}
// Driver code
public static void Main()
{
string str = "geeksforgeeks";
Console.Write(lexicographicallySmallest(str));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to find lexicographically
// smallest string formed by concatenating
// any prefix and its mirrored form
const lexicographicallySmallest = (str) => {
// Stores the largest prefix
// with character in decreasing
// order of ascii value
let prefix = "";
// Initialize prefix string
prefix += str[0];
// Loop to traverse the string
for (let i = 1; i < str.length; i++) {
// If current character is
// in decreasing order
if (str[i] < prefix[prefix.length - 1]) {
prefix += str[i];
}
else if (str[i] == prefix[prefix.length - 1]
&& prefix.length > 1) {
prefix += str[i];
}
else {
break;
}
}
// Stores the reversed prefix string
let rev = [...prefix];
rev.reverse();
// Return Answer
return prefix + rev.join("");
}
// Driver code
let str = "geeksforgeeks";
document.write(lexicographicallySmallest(str));
// This code is contributed by rakeshsahni
</script>
Producción
geeeeg
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA