Number of Atoms



C++ recursion solution
https://github.com/royalpranjal/LeetCode/blob/master/Number of Atoms.cpp

It's an interesting problem, but I don't think we have O(N) solution here.
All the solutions described above are O(N^2) and not O(N). In all of them we need to merge a internal formula into surrounding one, and thus if we have an input where the number of atoms is equal to number of nested formulas 
like A(B(C(D(E(F(G)2)2)2)2)2)2, then on every step the number of atoms to merge will increment  like 1, 2, 3, 4.. and therefore the total time is quadratic.Here's the code that generate 1m input and apparently doesn't complete in a reasonable time:
T = ('a','b','c', 'd', 'e', 'f', 'g')
S = ""for c1 in T:
for c2 in T:
for c3 in T:
for c4 in T:
for c5 in T:
for c6 in T:
for c7 in T:
S += c1.upper() + c2 + c3 + c4 + c5 + c6 + c7 + "("S += "H20"
for i in range(0, len(T) ** len(T)):
S += ")2"print("Number of atoms: " + str(len(S) / 10))
R = Solution().countOfAtoms(S)
print("Done: " + str(len(R)))
print("Result: " + R)


I don't think O(N^2) is a tight upper bound. The tighter bound would be O(BN) since each token will be looked at at most O(B) times, where B is the number of bracketed expressions.
For example,
 A(B(C(D(E(F3)4)5)6)7) > Here, B = O(N), so O(N^2)
 A(B(CDEFGHIJ)3)2 > Here, N >> B, and we parse, each element O(B) times, so O(BN)

Really great solutions! The following is the "missing" regular expression solution in Java :)
import java.util.regex.*; class Solution { public String countOfAtoms(String formula) { final Stack<Map<String, Integer>> stack = new Stack<>(); stack.push(new TreeMap<>()); final Pattern pattern = Pattern.compile("([AZ][az]*)(\\d*)(\\()(\\))(\\d*)"); final Matcher matcher = pattern.matcher(formula); while (matcher.find()) { final String match = matcher.group(); if (match.equals("(")) { stack.push(new TreeMap<>()); } else if (match.startsWith(")")) { final Map<String, Integer> top = stack.pop(); final int multiple = match.length() > 1 ? Integer.parseInt(match.substring(1, match.length())) : 1; for (final String name : top.keySet()) { stack.peek().put(name, stack.peek().getOrDefault(name, 0) + top.get(name) * multiple); } } else { int i = 1; while (i < match.length() && Character.isLowerCase(match.charAt(i))) { i++; } final String name = match.substring(0, i); final int count = i < match.length() ? Integer.parseInt(match.substring(i, match.length())) : 1; stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count); } } final StringBuilder sb = new StringBuilder(); for (final String name : stack.peek().keySet()) { sb.append(name); final int count = stack.peek().get(name); if (count > 1) { sb.append(String.valueOf(count)); } } return sb.toString(); } }

@Vroo How would you solve it on
O(D+E)
time? Do you have a sketch of your solution or an idea explaining the same?

@dribvurhd I said O(D+E) space, not time. O(D+E) time is not possible since it may be that D+E << N. Yes, I wrote the code. It scans the string just twice: once to tokenize and once to count. I posted my comment because I was surprised to see all accepted answers using O(N^2) time.

@Vroo Yes, you're right!
O(N)
w/o the sorting requirement with 2passes should be possible.