Number of Atoms

Moderate
0/80
Average time to solve is 50m
20 upvotes
Asked in company
Amazon

Problem statement

Given a string, representing a chemical formula, return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters follow, representing the name.

One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas can be concatenated together to produce another formula. For example, H2O2He3Mg4 is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O2)3 are formulas.

Given a formula, return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

Note : 
The given formula consists of English alphabets, digits, ‘(‘ and ’)’.

The given formula is always valid.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The only line of each test case contains a string representing the formula.
Output Format: 
For each test case, return the string representing the count of all the elements is printed.

The output for each test case is in a separate line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= |S| <= 10^4

Time Limit: 1 sec
Note : 
The count of each element in the formula will not exceed 2^31.
Sample Input 1:
2
H2O
Mg(OH)2
Sample Output 1:
H2O
H2MgO2
Explanation of the Sample Input 1:
The first formula contains two elements H and O, with their count as 2 and 1 respectively. Since the count of O is not greater than 1, it is printed as O only and H is printed as H2. 

The second formula contains three elements : Mg, O and H. Mg has a count of 1 and since O and H are in parentheses followed by the digit 2, both have a count of 2.
Sample Input 2:
1
K4(ON(SO3)2)2
Sample Output 2:
K4N2O14S4
Explanation of Sample Input 2
For the given formula, the elements are K, O, N and S. The count of K is 4, N is 2, O is 14 ( (1 + (3*2)) * 2 = 14) and that of S is 4 (2 * 2).
Sample Input 3
1
Be32
Sample Output 3
Be32
Hint

Try to recursively solve the problem and store the count of atoms in some suitable data structure.

Approaches (2)
Using recursion

The main idea behind this approach is to use recursion and find the count of atoms between a ‘(‘ and a ‘)’. Whenever we encounter a ‘(‘, we make a recursive call to the function, which after execution, gives an unordered map consisting of the count of atoms within the current formula. Then, we can use that map to calculate the count of atoms in a string containing that parenthesis.
 

Following is the algorithm for this approach :
 

  1. If we encounter alphabets/atoms, then add them to a string. If any lowercase letters follow, then append them to the string as well.
  2. If we encounter digits, then build the total value of the current number.
  3. After processing the alphabet and digit, add it to a UNORDERED_MAP<STRING, INT>
  4. If the Atom already exists in the map then add the digit to the existing value else just insert the atom with the digit.
  5. If we encounter '(' then recursively call the function with a new UNORDERED_MAP<STRING, INT> and repeat steps 1 to 4.
  6. Once we return from the recursive call process with the new map, add its <ATOM, VALUE> pairs to the existing map.
  7. Whenever we encounter ')', we will check if there is a digit following ')'. If yes, then we multiply that digit with all the values in the map.
  8. Now, we have the count of each element in the final map. Push all the elements and their respective counts from the map to a vector/list/array. Since we need the elements in sorted order, we sort these elements and then build a string from the final sorted structure.
Time Complexity

O(N^2), where N is the length of the formula.

It takes O(N) time to parse through the formula, but each of O(N) multiplicities after a bracket may increment the count of each name in the formula (inside those brackets), leading to an O(N^2) complexity. 
 

For example: For the formula A(B(C(D(E(F)2)2)2)2)2, the first multiplicity (the first 2 after F) will increment the count of F. Then, the next multiplicity (the second 2) will increment the count of both E and F and so on.
 

Also, since we are using an unordered_map, the time complexity of inserting elements will be O(1) and thus, the complexity for creating the final map with all the counts will be O(N * N * 1) = O(N ^ 2).
 

Now, creating a vector/list/array from the map will take O(N) time and sorting the structure will take O(N * log(N)) time. Thus, the final complexity will be O(N^2 + N + N*log(N)) = O(N ^ 2).

Space Complexity

O(N), where N is the length of the formula.
 

We are storing only the information that is already there in the formula. Thus, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Number of Atoms
Full screen
Console