Lexicographically largest string formed from the characters in range L and R
Given a string S and a range L and R, the task is to print the lexicographically largest string that can be formed from the characters in range L and R.
Examples:
Input: str = "thgyfh", L = 2, R = 6
Output: yhhgf
Input: str = "striver", L = 3, R = 5
Output: vri
Naive Approach:
- Extract the substring from index L to R from the given string.
- Sort the substring in descending order using any sorting algorithm.
- Return the sorted substring as the lexicographically largest string.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; string printLargestString(string s, int L, int R) { string sub = s.substr(L - 1, R - L + 1); sort(sub.rbegin(), sub.rend()); return sub; } int main() { string s = "striver" ; int L = 3, R = 5; cout << printLargestString(s, L, R) << endl; return 0; } |
Java
import java.util.Arrays; public class GFG { static String printLargestString(String s, int L, int R) { String sub = s.substring(L - 1 , R); char [] charArr = sub.toCharArray(); Arrays.sort(charArr); return new StringBuilder( new String(charArr)).reverse().toString(); } public static void main(String[] args) { String s = "striver" ; int L = 3 , R = 5 ; System.out.println(printLargestString(s, L, R)); } } // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Python3
# function to print the largest string def printLargestString(s, L, R): sub = s[L - 1 :R] sub = ''.join( sorted (sub, reverse = True )) return sub # Driver Program s = "striver" L = 3 R = 5 print (printLargestString(s, L, R)) # THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
C#
using System; class GFG { static string printLargestString( string s, int L, int R) { // Extract the substring from index L-1 to R string sub = s.Substring(L - 1, R - L + 1); // Convert the substring to a char array and sort it in descending order char [] chars = sub.ToCharArray(); Array.Sort(chars); Array.Reverse(chars); // Convert the sorted char array back to a string string result = new string (chars); return result; } static void Main( string [] args) { string s = "striver" ; int L = 3, R = 5; // Call the PrintLargestString function and print the result Console.WriteLine(printLargestString(s, L, R)); } } |
Javascript
// function to print the largest string function printLargestString(s, L, R) { let sub = s.substring(L - 1, R); let subArray = sub.split( '' ); subArray.sort((a, b) => b.localeCompare(a)); return subArray.join( '' ); } // Driver Program let s = "striver" ; let L = 3, R = 5; console.log(printLargestString(s, L, R)); // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Output
vri
Time Complexity: O(N log N), where N is the length of the substring (R – L + 1).
Auxiliary Space: O(R – L + 1) since we are creating a substring of length (R – L + 1) to sort it.
Approach:
- Iterate from min(L, R) to max(L, R) and increase the frequencies of characters in a freq[] array.
- Iterate from 25 to 0 and print the number of times every character occurs to get the lexicographically largest string.
The common point of mistake that everyone does is they iterate from L to R instead of min(L, R) to max(L, R).
Below is the implementation of the above approach:
C++
// C++ program to print the // lexicographically largest string that // can be formed from the characters // in range L and R #include <bits/stdc++.h> using namespace std; // Function to return the lexicographically largest string string printLargestString(string s, int l, int r) { // hash array int freq[26] = { 0 }; // make 0-based indexing l--; r--; // iterate and count frequencies of character for ( int i = min(l, r); i <= max(l, r); i++) { freq[s[i] - 'a' ]++; } // ans string string ans = "" ; // iterate in frequency array for ( int i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i]) { ans += char ( 'a' + i); freq[i]--; } } return ans; } // Driver Code int main() { string s = "striver" ; int l = 3, r = 5; cout << printLargestString(s, l, r); return 0; } |
Java
// Java program to print the // lexicographically largest String that // can be formed from the characters // in range L and R class GFG { // Function to return the lexicographically largest String static String printLargestString(String s, int l, int r) { // hash array int freq[] = new int [ 26 ]; // make 0-based indexing l--; r--; // iterate and count frequencies of character for ( int i = Math.min(l, r); i <= Math.max(l, r); i++) { freq[s.charAt(i) - 'a' ]++; } // ans String String ans = "" ; // iterate in frequency array for ( int i = 25 ; i >= 0 ; i--) { // add till all characters // are added while (freq[i] > 0 ) { ans += ( char ) ( 'a' + i); freq[i]--; } } return ans; } // Driver Code public static void main(String[] args) { String s = "striver" ; int l = 3 , r = 5 ; System.out.println(printLargestString(s, l, r)); } } /* This JAVA code is contributed by 29AjayKumar*/ |
Python 3
# Python 3 program to print the # lexicographically largest string that # can be formed from the characters # in range L and R # Function to return the lexicographically # largest string def printLargestString(s, l, r): # hash array freq = [ 0 ] * 26 # make 0-based indexing l - = 1 r - = 1 # iterate and count frequencies of character for i in range ( min (l, r), max (l, r) + 1 ) : freq[ ord (s[i]) - ord ( 'a' )] + = 1 # ans string ans = "" # iterate in frequency array for i in range ( 25 , - 1 , - 1 ): # add till all characters are added while (freq[i]): ans + = chr ( ord ( 'a' ) + i) freq[i] - = 1 return ans # Driver Code if __name__ = = "__main__" : s = "striver" l = 3 r = 5 print (printLargestString(s, l, r)) # This code is contributed by ita_c |
C#
// C# program to print the lexicographically // largest String that can be formed from the // characters in range L and R using System; class GFG { // Function to return the lexicographically // largest String static String printLargestString(String s, int l, int r) { // hash array int []freq = new int [26]; // make 0-based indexing l--; r--; // iterate and count frequencies // of character for ( int i = Math.Min(l, r); i <= Math.Max(l, r); i++) { freq[s[i] - 'a' ]++; } // ans String String ans = "" ; // iterate in frequency array for ( int i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i] > 0) { ans += ( char ) ( 'a' + i); freq[i]--; } } return ans; } // Driver Code public static void Main() { String s = "striver" ; int l = 3, r = 5; Console.Write(printLargestString(s, l, r)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript program to print the // lexicographically largest String that // can be formed from the characters // in range L and R // Function to return the lexicographically largest String function printLargestString( s , l , r) { // hash array var freq = Array(26).fill(0); // make 0-based indexing l--; r--; // iterate and count frequencies of character for (i = Math.min(l, r); i <= Math.max(l, r); i++) { freq[s.charCodeAt(i) - 'a' .charCodeAt(0)]++; } // ans String var ans = "" ; // iterate in frequency array for ( var i = 25; i >= 0; i--) { // add till all characters // are added while (freq[i] > 0) { ans += String.fromCharCode( 'a' .charCodeAt(0) + i); freq[i]--; } } return ans; } // Driver Code var s = "striver" ; var l = 3, r = 5; document.write(printLargestString(s, l, r)); // This code is contributed by todaysgaurav </script> |
Output
vri
Complexity Analysis:
- Time Complexity: O(N), as we are using a loop to traverse N times for counting the frequencies.
Each element gets added to the frequency table only once which takes O(1) and is appended to string which also takes O(1). - Auxiliary Space: O(N), as we are using extra space for storing resultant string.
Contact Us