Dado un número K y una string S, tenemos que encontrar la string str lexicográficamente más pequeña de longitud K tal que su conjunto de letras sea un subconjunto del conjunto de letras de S y S sea lexicográficamente más pequeño que str.
Ejemplos:
Input :k = 3 s = zbf Output: zbz Explanation: zbz is greater than zbf and it is smaller than any other lexicographically greater string than zbf Input :k = 3 s = gi Output: gig Explanation: gig > gi and size is 3.
Enfoque: si el tamaño de la string es menor que k, simplemente debemos agregar k – s.size() símbolos mínimos de s.
Si el tamaño de la string es mayor o igual a k, entonces debemos reemplazar todos los símbolos en el sufijo de los primeros k símbolos de los símbolos más pequeños de la string y reemplazar el carácter anterior a este sufijo con el siguiente carácter mayor existente en la string.
Nota: Si el índice k – 1 en la string contiene el carácter mayor, entonces retrocedemos un índice y retrocedemos hasta encontrar un carácter que no es igual al carácter mayor.
C++
// C++ implementation of above algorithm. #include <bits/stdc++.h> using namespace std; // function to print output void lexoString(string s, int k) { int n = s.size(); // to store unique characters of the string vector<char> v; // to check uniqueness map<char, int> mp; for (int i = 0; i < s.size(); i++) { if (mp[s[i]] == 0) { // if mp[s[i]] = 0 then it is // first time mp[s[i]] = 1; v.push_back(s[i]); } } // sort the unique characters sort(v.begin(), v.end()); // simply add n-k smallest characters if (k > n) { cout << s; for (int i = n; i < k; i++) { cout << v[0]; } return; // end the program } // searching the first character left of // index k and not equal to greatest // character of the string for (int i = k - 1; i >= 0; i--) { if (s[i] != v[v.size() - 1]) { for (int j = 0; j < i; j++) { cout << s[j]; } // finding the just next greater // character than s[i] for (int j = 0; j < v.size(); j++) { if (v[j] > s[i]) { cout << v[j]; break; } } // suffix with smallest character for (int j = i + 1; j < k; j++) cout << v[0]; return; } } // if we reach here then all indices to the left // of k had the greatest character cout << "No lexicographically greater string of length " << k << " possible here."; } // Driver code int main() { string s = "gi"; int k = 3; // Function call lexoString(s, k); return 0; }
Java
// Java implementation of above algorithm. import java.util.*; class GFG { // function to print output static void lexoString(char[] s, int k) { int n = s.length; // to store unique characters of the string Vector<Character> v = new Vector<>(); // to check uniqueness Map<Character, Integer> mp = new HashMap<>(); for (int i = 0; i < s.length; i++) { if (!mp.containsKey(s[i])) { // if mp[s[i]] = 0 then it is // first time mp.put(s[i], 1); v.add(s[i]); } } // sort the unique characters Collections.sort(v); // simply add n-k smallest characters if (k > n) { System.out.print(String.valueOf(s)); for (int i = n; i < k; i++) { System.out.print(v.get(0)); } return; // end the program } // searching the first character left of // index k and not equal to greatest // character of the string for (int i = k - 1; i >= 0; i--) { if (s[i] != v.get(v.size() - 1)) { for (int j = 0; j < i; j++) { System.out.print(s[j]); } // finding the just next greater // character than s[i] for (int j = 0; j < v.size(); j++) { if (v.get(j) > s[i]) { System.out.print(v.get(j)); break; } } // suffix with smallest character for (int j = i + 1; j < k; j++) { System.out.print(v.get(0)); } return; } } // if we reach here then all indices to the left // of k had the greatest character System.out.print("No lexicographically greater string of length " + k + " possible here."); } // Driver code public static void main(String arr[]) { String s = "gi"; int k = 3; // Function call lexoString(s.toCharArray(), k); } } // This code contributed by Rajput-Ji
Python3
# Python 3 implementation of above algorithm. # function to print output def lexoString(s, k): n = len(s) # to store unique characters # of the string v = [] # to check uniqueness mp = {s[i]:0 for i in range(len(s))} for i in range(len(s)): if (mp[s[i]] == 0): # if mp[s[i]] = 0 then it is # first time mp[s[i]] = 1 v.append(s[i]) # sort the unique characters v.sort(reverse = False) # simply add n-k smallest characters if (k > n): print(s, end = "") for i in range(n, k, 1): print(v[0], end = "") return; # end the program # searching the first character left of # index k and not equal to greatest # character of the string i = k - 1 while(i >= 0): if (s[i] != v[len(v) - 1]): for j in range(0, i, 1): print(s[j], end = " ") # finding the just next greater # character than s[i] for j in range(0, len(v), 1): if (v[j] > s[i]): print(v[j], end = " ") break # suffix with smallest character for j in range(i + 1, k, 1): print(v[0], end = " ") re1turn i -= 1 # if we reach here then all indices to # the left of k had the greatest character print("No lexicographically greater", "string of length", k, "possible here.") # Driver code if __name__ == '__main__': s = "gi" k = 3 # Function call lexoString(s, k) # This code is contributed by # Shashank_Sharma
C#
// C# implementation of above algorithm. using System; using System.Collections.Generic; class GFG { // function to print output static void lexoString(char[] s, int k) { int n = s.Length; // to store unique characters of the string List<char> v = new List<char>(); // to check uniqueness Dictionary<char, int> mp = new Dictionary<char, int>(); for (int i = 0; i < s.Length; i++) { if (!mp.ContainsKey(s[i])) { // if mp[s[i]] = 0 then it is // first time mp.Add(s[i], 1); v.Add(s[i]); } } // sort the unique characters v.Sort(); // simply add n-k smallest characters if (k > n) { Console.Write(String.Join("", s)); for (int i = n; i < k; i++) { Console.Write(v[0]); } return; // end the program } // searching the first character left of // index k and not equal to greatest // character of the string for (int i = k - 1; i >= 0; i--) { if (s[i] != v[v.Count - 1]) { for (int j = 0; j < i; j++) { Console.Write(s[j]); } // finding the just next greater // character than s[i] for (int j = 0; j < v.Count; j++) { if (v[j] > s[i]) { Console.Write(v[j]); break; } } // suffix with smallest character for (int j = i + 1; j < k; j++) { Console.Write(v[0]); } return; } } // if we reach here then all indices to the left // of k had the greatest character Console.Write("No lexicographically greater " + "string of length " + k + " possible here."); } // Driver code public static void Main(String []arr) { String s = "gi"; int k = 3; // Function call lexoString(s.ToCharArray(), k); } } // This code is contributed by Princi Singh
Javascript
<script> // JavaScript implementation of above algorithm. // function to print output function lexoString(s, k) { var n = s.length; // to store unique characters of the string var v = []; // to check uniqueness var mp = {}; for (var i = 0; i < s.length; i++) { if (!mp.hasOwnProperty(s[i])) { // if mp[s[i]] = 0 then it is // first time mp[s[i]] = 1; v.push(s[i]); } } // sort the unique characters v.sort((a, b) => a - b); // simply add n-k smallest characters if (k > n) { document.write(s.join("")); for (var i = n; i < k; i++) { document.write(v[0]); } return; // end the program } // searching the first character left of // index k and not equal to greatest // character of the string for (var i = k - 1; i >= 0; i--) { if (s[i] !== v[v.length - 1]) { for (var j = 0; j < i; j++) { document.write(s[j]); } // finding the just next greater // character than s[i] for (var j = 0; j < v.length; j++) { if (v[j] > s[i]) { document.write(v[j]); break; } } // suffix with smallest character for (var j = i + 1; j < k; j++) { document.write(v[0]); } return; } } // if we reach here then all indices to the left // of k had the greatest character document.write( "No lexicographically greater " + "string of length " + k + " possible here." ); } // Driver code var s = "gi"; var k = 3; // Function call lexoString(s.split(""), k); </script>
gig
Complejidad de tiempo: O(k + s.size())
Publicación traducida automáticamente
Artículo escrito por Bibhu Pala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA