Lexicographically next greater string using same character set
Given a number K and a string S, We have to Find the lexicographically smallest string str of length K such that it’s set of letters is a subset of the set of letters of S and S is lexicographically smaller than str.
Examples:
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.
Approach: If size of string is less than k, we should simply add k – s.size() minimum symbols from s.
If the size of the string is greater than or equal to k then we need to replace all symbols in the suffix of first k symbols of string smallest symbols and replace the character before this suffix with next greater character existing in the string.
Note: If k – 1 index in string holds the greatest character then we move one index back and we move back until we find a character which is not equal to the greatest character.
Implementation:
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
Time Complexity : O(k + s.size())