String Reformat

Easy
0/40
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
Google inc

Problem statement

You are given a string ‘S’ consisting of alphanumeric characters, the string divided into groups by a ‘-’. Your task is to reformat the string that all the groups contain exactly ‘K’ characters. All the lowercase characters should be converted to uppercase.

Note: 
The first group may have fewer characters than ‘K’.
For example: 
You are given ‘S’ =’A1-ijklmno-pqr’ and k = ‘3’, then the string contains 3 parts, [“A1”, “ijklmno”, “pqr”], then you can form the string in groups ["A1I”, “JKL”, “MNO”, “PQR"] of uppercase characters. Hence the answer is "A1I-JKL-MNO-PQR"
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
 The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains one integer ‘K’, representing the size of the group the string is to be divided.

The second line of each test case contains the string ‘S’ representing the given string.
Output Format: 
For each test case, print a single string consisting of alphanumeric characters divided into groups of size ‘K’ separated by ‘-’.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= K <= 10^8
1 <= |S| <= 10^8

All characters in ‘S’ are alphanumeric and ‘-’.

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
3
Ab-ijklmno-pqr
4
Isa-dkj
Sample Output 1:
ABI-JKL-MNO-PQR
IS-ADKJ
Explanation:
For the first test case ‘S’ = ’Ab-ijklmno-pqr’ and ‘K’ = ‘3’, then the string contains 3 groups, [“Ab”, “ijklmno”, “pqr”], then you can form the string in groups ["ABI”, “JKL”, “MNO”, “PQR"] of uppercase characters. Hence the answer is "ABI-JKL-MNO-PQR".

For the second test case ‘S’ = “Isa-dkj” and ‘K’ = ‘4’, then the string contains 2 groups, [“Isa”, “dkj”], then you can form the string in groups ["IS”, “ADKJ”] of uppercase characters. Hence the answer is "IS-ADKJ".
Sample Input 2:
2
2
a-b-1
1
abcdef
Sample Output 2:
A-B1
A-B-C-D-E-F
Hint

Try to remove the separator from the string.

Approaches (1)
Iterative Approach

In this approach, we will remove the separator ‘-’,  Then we will move from the end towards the starting of the string and add a  ‘-’ after each k character of the string.

 

Algorithm:

  • Initialise an empty string ansStr
  • Iterate i from length of s  - 1 to 0
    • If s[i] is equal to ‘-’
      • Continue the loop
    • If the size ansStr mod with k + 1 equals to k
      • Add ‘-’ to ansStr
    • Add upper case character at s[i] to ansStr
  • Reverse the string ansStr
  • Finally, return the string ansStr
Time Complexity

O(N), Where N is the length of the string.

 

We are iterating over the string once, which will take O(N) time. Hence the overall time complexity is O(N).

Space Complexity

O(N), Where N is the length of the string.

 

We have to maintain the result string, which will take O(N) space in the worst case. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
String Reformat
Full screen
Console