Smallest string

Easy
0/40
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in companies
OracleAdobePracto

Problem statement

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".
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 29
3 42
Sample Output 1:
aaaay 
aoz
Explanation of Sample Input 1:
Test Case 1: The  numeric value of  “aaaay”  is 1+1+1+1+25
This is the shortest lexicographic string with length ‘5’ and numeric value 29.

It can be verified that for any other combination of alphabets with the given numeric value, ‘aaazy’ is the lexicographically smallest.

Test Case 2: The lexicographic smallest string of length 3 and numeric value 42 is “aoz”.

It can be verified that for any other combination of alphabets with the given numeric value, ‘aoz’ is the lexicographically smallest.
Sample Input 2:
2
1 6
2 2
Sample Output 2:
f
aa
Hint

For lexicographically shortest string, try to place as many ‘a’ in starting and ‘z’ in the end.

Approaches (1)
Simple Approach

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’.
Time Complexity

O( N ), where ‘N’ is the length of the string formed.

 

We are forming a string of length ‘N’ in a single traversal. So the time complexity is O( N ).

Space Complexity

O( N ),  where ‘N’ is the length of the string formed.

 

We are using a resultant string of length ‘N’, making space complexity O( N ).

Code Solution
(100% EXP penalty)
Smallest string
Full screen
Console