Last Updated: 9 Apr, 2021
Smallest string
Easy
Asked in companies
You are given two integers, ‘N’ and ‘V’. You need to construct a string having length ‘N’ and numeric value ‘V’.
The numeric value of a character is determined by its position in alphabets( 1- indexed)
For Example-
The numeric value of ‘a’ is 1, ‘b’ is 2.
The numeric value of a string is determined by adding the numeric value of all its characters.
For Example -
The numeric value of “bde” is 2 + 4 + 5, i.e. 11.
Example:
If 'N' = 3 and 'V' = 10, you need to construct string as “aah".
Input Format:
The first line contains a single integer ‘T’, denoting the number of test cases.
Each test case’s first line contains two space-separated integers, ‘N’, denoting the string’s length to construct, ‘V’, denoting the string’s required numeric value.
Output Format:
For each test case, return the lexicographically string having the length ‘N’ and numeric value ‘V’.
Note:
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^5
N <= V <= 26*N
Time Limit: 1 sec
Approaches
The basic idea is that we will try to place characters with maximum numeric value at the end of the string for the lexicographically smallest string. That means we want as many a’s at the start of the string and z’s at the end of the sting.
So we will first initialize a string of length ‘N’ with all the characters ‘a’ and decrement ‘V’ by ‘N’. Now placing ‘ z ’ at any position will increment the numeric value of the string by 25. So we will traverse the string from the end and place ‘z’ at positions (i.e. increment character value by 25 ) and decrement ‘V’ by 25 until the given string value is not obtained. If at any point V < 25 that means placing ‘z’ will exceed the given string value so Increment the character value with exactly ‘V’.
Algorithm
- Create a string ‘S’ of length ‘N’ with all characters as ‘a’.
- Decrement ‘V’ by ‘N’.
- Initialize a variable ‘index’ that will store an index to string at which we have to change character. ( initially pointing to ending index of the string).
- Run a loop until ‘V’ >0
- Increment S[ index ] by a minimum of V and 25.
- Decrement ‘V’ by a minimum of V and 25.
- Return ‘S’.