Last Updated: 6 Jul, 2022
String Sum
Moderate
Asked in company
Dhoni is the security administrator of the company you are working and you are junior to him. Dhoni’s job is to come up with new and innovative encryption algorithms to encrypt the data while sending it to the receiver.
He came up with a new encryption algorithm as follows: Let’s suppose there is a string ‘STR’ of length ‘N’ which consists of lowercase English letters and numbers from ‘0’ to ‘9’.
The above algorithm will first find the total of all the digits occurring in the string ‘STR’ and remove them from the string, then will sort the whole string in alphabetical order and push all digits sum at the end of the above-generated string. In case there is no digit present in the given string, we don't add anything at the end.
He is analyzing how effective this algorithm will be so he asked you to automate this process so that he gets the results quicker.
So can you help hip to automate this process?.
NOTE: The sum of numbers occurring in the string may have more than one digit.
EXAMPLE :
Input: ‘N’ = 7, ‘STR’ = ac2bew3
Output: abcew5
In this case, the digit occurring in the ‘STR’ is ‘2’ and ‘3’. Their sum is ‘5’. And when we sort the letters in alphabetical order we get “abcew”. Hence the concatenation of both is “abcew5”.
Input Format :
The first line will contain the integer 'T', the number of test cases.
Each test case consists of two lines.
The first line of input contains one integer, ‘N’ the length of the string ‘STR’.
Followed by a line containing the string ‘STR’ of length ‘N’.
Output format :
For each test case, print the final string obtained after performing the mentioned steps.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
‘STR’ consists of lowercase letters or digits.
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
Approaches
The idea for this approach is to divide the whole process into two parts. The first part will involve doing the sum of all the digits present in the string ‘STR’. The second part will involve the ordering of letters in alphabetical order. And then we concatenate the results of both parts and get the final result.
To solve the first part we will iterate on the given string and whenever we find a digit we add it to a variable sum. And then we create a string of that number.
For the second part, we will first, create a new string that will only contain all the letters in the given string ‘STR’. Then we will sort the letters in alphabetical order.
We can sort the letters in alphabetical order using any O(N*log(N)) algorithm for better time complexity.
Then we merge the results of both parts and return them.
Algorithm:
// The function will return true if the given character is a number.
Int isDigit(X)
- If X lies in the range ‘0’ to ‘9’.
- Return the value of ‘X’ in the decimal system.
- Return ‘-1’.
// The function will return the final string after performing given operations.
String stringSum(N, STR)
- Initialize a variable named ‘SUM’ with the value of ‘0’.
- Initialize a variable names ‘digitFound’ with the value of ‘FALSE’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘DIGIT’ with the value of ‘isDigit(STR[i])’.
- If ‘DIGIT != -1’
- Add ‘DIGIT’ to ‘SUM’.
- Assign ‘digitFound’ the value of ‘TRUE’.
- Initialize a string with the name ‘charStr’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘DIGIT’ with the value of ‘isDigit(STR[i])’.
- If ‘DIGIT == -1’
- Add ‘STR[i]’ to ‘charStr’.
- Sort the ‘charStr’ string in alphabetical order.
- If ‘digitFound == TRUE’
- Add the string formed by converting ‘SUM’ into the string format to the ‘charStr’ string.
- Return ‘charStr’.
The idea for this approach is similar to the previous sorting approach, but instead of an O(N*log(N)) algorithm for sorting, we will use the counting sort approach to sort the string formed by letters of ‘STR’ in O(N).
So we can observe that there can be at most ‘26’ distinct letters present in the given string ‘STR’. We can track the frequency of each letter using an array of size ‘26’. Then in another pass, we can use this frequency to know how many occurrences of each letter is to be added to the final string. We can start the iteration of the array from ‘a’ up to ‘z’. In this counting we consider value of ‘a’ = 0, ‘b’ = 1, … , ‘z’ = 25.
Similar to the sorting approach we will create a string formed by the sum and append it to the end of the string generated by ordering the letters in alphabetical order and then return their concatenation.
Algorithm:
// The function will return true if the given character is a number.
Int isDigit(X)
- If X lies in the range ‘0’ to ‘9’.
- Return the value of ‘X’ in the decimal system.
- Return ‘-1’.
// The function will return the final string after performing given operations.
String stringSum(N, STR)
- Initialize a variable named ‘SUM’ with the value of ‘0’.
- Initialize a variable names ‘digitFound’ with the value of ‘FALSE’.
- Initialize a variable named ‘maxChar’ with the value of ‘26’.
- Initialize an array ‘countOfLetters’ with the size of ‘maxChar’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘DIGIT’ with the value of ‘isDigit(STR[i])’.
- If ‘DIGIT != -1’
- Add ‘DIGIT’ to ‘SUM’.
- Assign ‘digitFound’ the value of ‘TRUE’.
- Else
- Increase the count of the number corresponding to ‘STR[i]’ in ‘countOfLetters’.
- Initialize a string with the name ‘charStr’.
- Run a for loop from ‘0’ to ‘maxChar-1’ with a variable named ‘i’.
- Run a while loop until ‘countOfLetters[i] != 0’.
- Add the character corresponding to ‘i’ to ‘charStr’.
- Decrement ‘countOfLetters[i]’ by one.
- Run a while loop until ‘countOfLetters[i] != 0’.
- If ‘digitFound == TRUE’
- Add the string formed by converting ‘SUM’ into the string format to the ‘charStr’ string.
- Return ‘charStr’.