Lexicographically largest string with sum of characters equal to N
Given a positive integer N, the task is to find the lexicographically largest string consisting of lower-case English alphabets such that the sum of the characters of the string equals N where ‘a’ = 1, ‘b’ = 2, ‘c’ = 3, ….. , and ‘z’ = 26.
Examples:
Input: N = 30
Output: zd
Explanation:
The lexicographically largest string formed is “zd” whose sum of position of characters is (26 + 4) = 30(= N).Input: N = 14
Output: n
Approach: To make lexicographically the largest string, the idea is to print the character z, N/26 number of times and then the character at (N%26 + 1)th position in the English alphabets. Follow the steps below to solve the problem:
- Initialize a string, say ans, that stores the required lexicographically largest string.
- Iterate until N is at least 26 and perform the following steps:
- Add the character z to the string ans.
- Decrement the value of N by 26.
- Add the value of char(N + ‘a’) to the string ans.
- After completing the above steps, print the value of ans as the resultant string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to construct the // lexicographically largest string // having sum of characters as N string getString( int N) { // Stores the resulting string string ans = "" ; // Iterate until N is at least 26 while (N >= 26) { // Append 'z' to the string ans ans += 'z' ; // Decrement N by 26 N -= 26; } // Append character at index (N + 'a') ans += char (N + 'a' - 1); // Return the resultant string return ans; } // Driver Code int main() { int N = 30; cout << getString(N); return 0; } |
Java
// java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to construct the // lexicographically largest string // having sum of characters as N static String getString( int N) { // Stores the resulting string String ans = "" ; // Iterate until N is at least 26 while (N >= 26 ) { // Append 'z' to the string ans ans += 'z' ; // Decrement N by 26 N -= 26 ; } // Append character at index (N + 'a') ans += ( char )(N + 'a' - 1 ); // Return the resultant string return ans; } // Driver Code public static void main(String[] args) { int N = 30 ; System.out.print(getString(N)); } } // This code is contributed by Kingash. |
Python3
# Python3 program for the above approach # Function to construct the # lexicographically largest string # having sum of characters as N def getString(N): # Stores the resulting string ans = "" # Iterate until N is at least 26 while (N > = 26 ): # Append 'z' to the string ans ans + = 'z' # Decrement N by 26 N - = 26 # Append character at index (N + 'a') ans + = chr (N + ord ( 'a' ) - 1 ) # Return the resultant string return ans # Driver Code if __name__ = = '__main__' : N = 30 print (getString(N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; public class GFG { // Function to construct the // lexicographically largest string // having sum of characters as N static string getString( int N) { // Stores the resulting string string ans = "" ; // Iterate until N is at least 26 while (N >= 26) { // Append 'z' to the string ans ans += 'z' ; // Decrement N by 26 N -= 26; } // Append character at index (N + 'a') ans += ( char )(N + 'a' - 1); // Return the resultant string return ans; } // Driver Code public static void Main( string [] args) { int N = 30; Console.WriteLine(getString(N)); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to construct the // lexicographically largest string // having sum of characters as N function getString(N){ // Stores the resulting string let ans = "" // Iterate until N is at least 26 while (N >= 26){ // Append 'z' to the string ans ans += 'z' // Decrement N by 26 N -= 26 } // Append character at index (N + 'a') ans += String.fromCharCode(N + 'a' .charCodeAt(0) - 1) // Return the resultant string return ans } // Driver Code let N = 30 document.write(getString(N)) // This code is contributed by Saurabh Jaiswal </script> |
Output:
zd
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us