I would love a 1 hr video to go over alternative solutions or going through how you think in a thorough way or certain patterns you noticed that could be applied to other problems. More information always helps :) thank you!
The problem with that alternative solution is, it is not that efficient. I wrote that recursive solution itself first, but was like bottom 40 %tile in both speed and memory.
Hi, can you provide some context onto what you're talking about? How did you relate this to compilers? Some examples would help. Just curious :)) I have that course next semester so looking forward to it.
@@peakchinmayism I think he's talking about the parsing part, doing the parsing of a compiler makes it much more easier to do the parsing of this problem.
@@peakchinmayism it is like the thing that reads your code and translates it into either machine code or assembly.. etc, in this problem we deal with string input and return the correct form so its kinda like leetcode is the programmer writing code and you're translating it to the correct form its essentially just that, i recommend you start learning C++ if you haven't already and maybe dig deeper into compilers they are a great way to reinforce your understanding of how the underlying programming language works
@@pastori2672 oh I got what you're trying to say. Thank you! I'm well versed in C++ though, don't have any experience with compilers yet. Looking forward to it.
Yeah Neetcode I use to be a Java dude, but as you said I've joined python church like a year ago... seems like I miss Java but I also have a good run with python so far. 🙏Thanks for all the effort you've given to series of these priceless videos.
I got it in 44 lines class Solution { public: string countOfAtoms(string formula) { stack st; map m; int n = formula.size(); int i = 0; while (i < n) { if (formula[i] == '(') { st.push(m); m.clear(); i++; } else if (formula[i] == ')') { int i_start = ++i, multiplicity = 1; while (i < n && isdigit(formula[i])) i++; if (i > i_start) multiplicity = stoi(formula.substr(i_start, i - i_start)); if (!st.empty()) { auto top = st.top(); st.pop(); for (auto &p : m) top[p.first] += p.second * multiplicity; m = top; } } else { int i_start = i++; while (i < n && islower(formula[i])) i++; string name = formula.substr(i_start, i - i_start); int i_start2 = i, multiplicity = 1; while (i < n && isdigit(formula[i])) i++; if (i > i_start2) multiplicity = stoi(formula.substr(i_start2, i - i_start2)); m[name] += multiplicity; } } string result; for (const auto &p : m) { result += p.first; if (p.second > 1) result += to_string(p.second); } return result; } };
Hey nice approach. But I think if we traverse from the end of the formula it will be easier just keep a stack of the numbers and a value of the multiplied numbers till now . I'm sorry Im bad at explaining over comments
Easier approach, the one I had in mind is to use a stack to track the multiplication factor whenever you step into a pair of brackets and when you step out, simply divide. The way to know the value you are going to multiply with, either pre-process the input to figure out the values and hash each bracket index to its value, or you could start backwards where you have the value before processing the inner string, I prefer the first one eaiser to code although more space but we already paying that... anyway this was much easier than the stack of hashmaps, thought of sharing it..
Traversing the formula backward takes O(N). Then sort the built array and collect elements joining adjacent the same ones. Sorting takes O(n log n) time
The code will fail for "Mg(Uub)2" , we need to do slight change in solution at line 21 and 22 and change it to below while i+1 < len(formula) and formula[i+1].islower(): element += formula[i+1] i+=1
Took about 60 lines to write in JavaScript. Here are my lessons: JavaScript has Regular Expressions. checking characters are even easier than Python. (as you know how to write it) Never use square brackets in JavaScript Map, always use get() and set().
I had around 110 lines using C++ (brackets matching to create a stack of multipliers) admittedly there was some whitespace of course but it was a slog and it took me around an hour so not sure how this could be done in an interview setting.
I thought of this approach and tried to make it work using a stack and a dictionary for about an hour, but I never knew you could store dictionaries in a stack (I know it's basic stuff). I thought it was ridiculous( I still do).
if you look at the code, his stack is just a python list, and you can store anything in those. The important thing is to pop and add elements in the correct order.
That was really hard to code and follow even though after your explanation that solution kind of makes sense. I wouldn't image who could do that in a real interview in under 45 mins if that was a new problem for that person. Hmm, I wonder if I want to get a job at google I should solve these problems easily? P.S. In TS I've got 67 lines of code vs your 38 - omg!
lets convert input "Mg(OH)2" to ['Mg', '(', 'O', 'H', ')', '2'] , it will be easy to code and get the output class Solution: def preProcess(self,formula): fm = [] for f in formula: if f.islower() or (f.isdigit() and fm[-1].isdigit()): fm[-1]+=f else: fm.append(f) return fm def countOfAtoms(self, formula: str) -> str: hm = dict() formula = [""]+self.preProcess(formula)[::-1]+[""] d = 1 n = len(formula) stack = [] for i in range(1,n): f = formula[i] pf = formula[i-1] if f.isdigit(): d = d * int(f) elif f == ')': stack.append(pf) elif f == '(': x = stack.pop() if x.isdigit(): d = d//int(x) else: hm[f] = hm.get(f,0) + d if pf.isdigit(): d = d//int(pf) ans = list(hm.items()) ans.sort() final = "" for f,n in ans: if n == 1: final += f else: final += f + str(n) return final
The java solution isn't that bad! Here's a 66 line solution similar to yours. ``` class Solution { public String countOfAtoms(String formula) { Stack stack = new Stack(); stack.push(new HashMap()); int i = 0; int n = formula.length();
while (i < n) { if (formula.charAt(i) == '(') { stack.push(new HashMap()); i++; continue; } if (formula.charAt(i) == ')') { i++; int count = 0; while (i < n && Character.isDigit(formula.charAt(i))) { count *= 10; count += (formula.charAt(i) - '0'); i++; } count = Math.max(count, 1); Map map = stack.pop(); Map prevMap = stack.peek(); for (String s : map.keySet()) { prevMap.put(s, prevMap.getOrDefault(s, 0) + (map.get(s) * count)); } continue; } StringBuilder sb = new StringBuilder(); sb.append(formula.charAt(i)); i++; while (i < n && Character.isLowerCase(formula.charAt(i))) { sb.append(formula.charAt(i)); i++; } int count = 0; while (i < n && Character.isDigit(formula.charAt(i))) { count *= 10; count += (formula.charAt(i) - '0'); i++; } String name = sb.toString(); count = Math.max(count, 1); Map map = stack.peek(); map.put(name, map.getOrDefault(name, 0) + count); } Map map = stack.peek(); List keys = new ArrayList(map.keySet()); Collections.sort(keys); StringBuilder sb = new StringBuilder(); for (String key : keys) { sb.append(key); int count = map.get(key); if (count > 1) { sb.append(count); } } return sb.toString(); } } ```
A lengthy code without stack of map class Solution: def countOfAtoms(self, formula: str) -> str: stack = [] i, n = 0, len(formula) while i < n: if formula[i] == ")": num = "" while i + 1 < n and formula[i + 1].isnumeric(): num += formula[i + 1] i += 1 num = int(num) if num else 1 arr = [] while stack[-1] != "(": if stack[-1].isnumeric(): new_frequency = num * int(stack.pop()) arr.append(str(new_frequency)) else: arr.append(stack.pop()) stack.pop() arr.reverse() stack.extend(arr) elif formula[i].isupper(): element, frequency = formula[i], "" while i + 1 < n and formula[i + 1].islower(): element += formula[i + 1] i += 1 while i + 1 < n and formula[i + 1].isnumeric(): frequency += formula[i + 1] i += 1 stack.append(element) stack.append(frequency if frequency else "1") else: stack.append(formula[i]) i += 1 freq_map = Counter() for i in range(0, len(stack), 2): freq_map[stack[i]] += int(stack[i + 1]) ans = "" for c in sorted(freq_map.keys()): if freq_map[c] == 1: ans += c else: ans += c + str(freq_map[c]) return ans
Python is basically sudo code if you can understand the sudocode then you can code it in any language. Edit - Sorry I did not saw the video and commented. I guess Navdeep need to avoid build-in python functions.
Isn't this incorrect. The problem specifically states that there will be "zero or more lowercase characters"... Considering only two is against the problem description
wtf!! i did not solved the question yet but approach to solve this question is very simple. why the fuck this video is 33min long. what am i missing ??
I would love a 1 hr video to go over alternative solutions or going through how you think in a thorough way or certain patterns you noticed that could be applied to other problems. More information always helps :) thank you!
The problem with that alternative solution is, it is not that efficient. I wrote that recursive solution itself first, but was like bottom 40 %tile in both speed and memory.
I really loved the way you started the video
Literally only reason why I watched the whole thing
As a java coder, I'm joining the python bandwagon
welcome to the gang yo
We can't give up yet.
ngl having some sort of experience with compilers made this a LOT easier to come up with and understand
Hi, can you provide some context onto what you're talking about? How did you relate this to compilers? Some examples would help.
Just curious :)) I have that course next semester so looking forward to it.
@@peakchinmayism I think he's talking about the parsing part, doing the parsing of a compiler makes it much more easier to do the parsing of this problem.
@@peakchinmayism it is like the thing that reads your code and translates it into either machine code or assembly.. etc, in this problem we deal with string input and return the correct form so its kinda like leetcode is the programmer writing code and you're translating it to the correct form its essentially just that, i recommend you start learning C++ if you haven't already and maybe dig deeper into compilers they are a great way to reinforce your understanding of how the underlying programming language works
@@pastori2672 oh I got what you're trying to say. Thank you!
I'm well versed in C++ though, don't have any experience with compilers yet. Looking forward to it.
Yeah Neetcode I use to be a Java dude, but as you said I've joined python church like a year ago... seems like I miss Java but I also have a good run with python so far. 🙏Thanks for all the effort you've given to series of these priceless videos.
Major respect to those spending their Saturday night solving this behemoth.
now try recursive solution lol
Being an indian, I read behemoth as "behenchod" 😂😂
@@kalmyk I swear the recursive solution is intuitive. Maybe it's because our university started out with recursion in the first semester.😀
Love the dedication to post daily videos !
I did using C++
134 lines of code phew!
I got it in 44 lines
class Solution {
public:
string countOfAtoms(string formula) {
stack st;
map m;
int n = formula.size();
int i = 0;
while (i < n) {
if (formula[i] == '(') {
st.push(m);
m.clear();
i++;
} else if (formula[i] == ')') {
int i_start = ++i, multiplicity = 1;
while (i < n && isdigit(formula[i])) i++;
if (i > i_start) multiplicity = stoi(formula.substr(i_start, i - i_start));
if (!st.empty()) {
auto top = st.top(); st.pop();
for (auto &p : m) top[p.first] += p.second * multiplicity;
m = top;
}
} else {
int i_start = i++;
while (i < n && islower(formula[i])) i++;
string name = formula.substr(i_start, i - i_start);
int i_start2 = i, multiplicity = 1;
while (i < n && isdigit(formula[i])) i++;
if (i > i_start2) multiplicity = stoi(formula.substr(i_start2, i - i_start2));
m[name] += multiplicity;
}
}
string result;
for (const auto &p : m) {
result += p.first;
if (p.second > 1) result += to_string(p.second);
}
return result;
}
};
Hey nice approach. But I think if we traverse from the end of the formula it will be easier just keep a stack of the numbers and a value of the multiplied numbers till now . I'm sorry Im bad at explaining over comments
No, it makes sense, I seewhat tou mean it's a great idea!
Kinda proud to be able to solve this by myself, especially in Java... Even though it took over an hour.
Easier approach, the one I had in mind is to use a stack to track the multiplication factor whenever you step into a pair of brackets and when you step out, simply divide. The way to know the value you are going to multiply with, either pre-process the input to figure out the values and hash each bracket index to its value, or you could start backwards where you have the value before processing the inner string, I prefer the first one eaiser to code although more space but we already paying that... anyway this was much easier than the stack of hashmaps, thought of sharing it..
We are waiting for an hour-long analysis of the problem))
Traversing the formula backward takes O(N). Then sort the built array and collect elements joining adjacent the same ones. Sorting takes O(n log n) time
Knowing Go or Python is a blessing.
I really appreciate your hard work and dedication to solve problems for us.
Thanks a lot Sir...🤗🤗🤗
Thank you so much.
Watched this video and implemented in C++ on my own and got accepted
Very nice explanation. Thanks for simplifying the complex hard problem and making it clear and simple.
The code will fail for "Mg(Uub)2" , we need to do slight change in solution at line 21 and 22 and change it to below
while i+1 < len(formula) and formula[i+1].islower():
element += formula[i+1]
i+=1
Uub is from the old periodic table, all elements have at most two characters now
I tried the same way but i dont manage code like you do. You have a way of simplifying thr algorithm and coding.
Don't u think it would easy using a recursive method which keeps iterating from the Back of the String??
Took about 60 lines to write in JavaScript. Here are my lessons:
JavaScript has Regular Expressions. checking characters are even easier than Python. (as you know how to write it)
Never use square brackets in JavaScript Map, always use get() and set().
Thanks
I had around 110 lines using C++ (brackets matching to create a stack of multipliers) admittedly there was some whitespace of course but it was a slog and it took me around an hour so not sure how this could be done in an interview setting.
65 lines
@@sojwalgosavi4406 Impressive my guy, could you maybe link your code if convenient.
how long did u take to solve it by urself ?
Great explanation and the code is very easy to comprehend
Java solution in 50 lines
class Solution {
public String countOfAtoms(String formula) {
int n=formula.length();
Stack stc=new Stack();
Map sMap=new TreeMap();
stc.push(sMap);
for(int i=0;i
I don't mind if it is half hr or one hr or 2 hr video just for a single question. I would just love to grasp every bit of it.
Really frustrating in Cpp as well, problem seems to be lengthiest, but no simple solution found, logically not tough
Thankyou for mentioning the Java developers.
You save my weekend. Thanks my hero.
I thought of this approach and tried to make it work using a stack and a dictionary for about an hour, but I never knew you could store dictionaries in a stack (I know it's basic stuff). I thought it was ridiculous( I still do).
if you look at the code, his stack is just a python list, and you can store anything in those. The important thing is to pop and add elements in the correct order.
poured a cup of tea, opened proble,, 37 mins of thinking & coding, done, tea cold
hii there , how many question have u solved on leetcode?
i started two month ago i solved 70 question , what is roadmap please help me.
I am Java person! thank you for the video :)
class Solution:
#TC:O(n^2)
#SC:O(n)
# Stack of hashmaps
def countOfAtoms(self, formula: str) -> str:
stack = [defaultdict(int)]
i = 0
while i < len(formula):
if formula[i] == '(':
stack.append(defaultdict(int))
elif formula[i] == ')':
curr_map = stack.pop()
prev_map = stack[-1]
count = ""
cnt = 1
while i+1
Thank you for the explanation
This was a really fun one
make 1hr videos and explain all the possible solutions
No need
very cool problem,
at least I come up with good question understanding😅
Hmm looks like I'm skipping this one, but it seems this does get easier after really understanding what the problem actually asks.
That was really hard to code and follow even though after your explanation that solution kind of makes sense.
I wouldn't image who could do that in a real interview in under 45 mins if that was a new problem for that person.
Hmm, I wonder if I want to get a job at google I should solve these problems easily?
P.S. In TS I've got 67 lines of code vs your 38 - omg!
lets convert input "Mg(OH)2" to ['Mg', '(', 'O', 'H', ')', '2'] , it will be easy to code and get the output
class Solution:
def preProcess(self,formula):
fm = []
for f in formula:
if f.islower() or (f.isdigit() and fm[-1].isdigit()):
fm[-1]+=f
else:
fm.append(f)
return fm
def countOfAtoms(self, formula: str) -> str:
hm = dict()
formula = [""]+self.preProcess(formula)[::-1]+[""]
d = 1
n = len(formula)
stack = []
for i in range(1,n):
f = formula[i]
pf = formula[i-1]
if f.isdigit():
d = d * int(f)
elif f == ')':
stack.append(pf)
elif f == '(':
x = stack.pop()
if x.isdigit(): d = d//int(x)
else:
hm[f] = hm.get(f,0) + d
if pf.isdigit():
d = d//int(pf)
ans = list(hm.items())
ans.sort()
final = ""
for f,n in ans:
if n == 1:
final += f
else:
final += f + str(n)
return final
traversing backwards makes this slightly simpler
it took me 2 hours to code this mammoth solution without seeing any solution
G.O.A.T!! 🙌🏻🙌🏻🙌🏻🙌🏻
Keep the max 30 minutes Solutions but add bonus solutions at the end.
this question was something a hell lot
The java solution isn't that bad! Here's a 66 line solution similar to yours.
```
class Solution {
public String countOfAtoms(String formula) {
Stack stack = new Stack();
stack.push(new HashMap());
int i = 0;
int n = formula.length();
while (i < n) {
if (formula.charAt(i) == '(') {
stack.push(new HashMap());
i++;
continue;
}
if (formula.charAt(i) == ')') {
i++;
int count = 0;
while (i < n && Character.isDigit(formula.charAt(i))) {
count *= 10;
count += (formula.charAt(i) - '0');
i++;
}
count = Math.max(count, 1);
Map map = stack.pop();
Map prevMap = stack.peek();
for (String s : map.keySet()) {
prevMap.put(s, prevMap.getOrDefault(s, 0) + (map.get(s) * count));
}
continue;
}
StringBuilder sb = new StringBuilder();
sb.append(formula.charAt(i));
i++;
while (i < n && Character.isLowerCase(formula.charAt(i))) {
sb.append(formula.charAt(i));
i++;
}
int count = 0;
while (i < n && Character.isDigit(formula.charAt(i))) {
count *= 10;
count += (formula.charAt(i) - '0');
i++;
}
String name = sb.toString();
count = Math.max(count, 1);
Map map = stack.peek();
map.put(name, map.getOrDefault(name, 0) + count);
}
Map map = stack.peek();
List keys = new ArrayList(map.keySet());
Collections.sort(keys);
StringBuilder sb = new StringBuilder();
for (String key : keys) {
sb.append(key);
int count = map.get(key);
if (count > 1) {
sb.append(count);
}
}
return sb.toString();
}
}
```
1 hour? no problem let's do it!
A lengthy code without stack of map
class Solution:
def countOfAtoms(self, formula: str) -> str:
stack = []
i, n = 0, len(formula)
while i < n:
if formula[i] == ")":
num = ""
while i + 1 < n and formula[i + 1].isnumeric():
num += formula[i + 1]
i += 1
num = int(num) if num else 1
arr = []
while stack[-1] != "(":
if stack[-1].isnumeric():
new_frequency = num * int(stack.pop())
arr.append(str(new_frequency))
else:
arr.append(stack.pop())
stack.pop()
arr.reverse()
stack.extend(arr)
elif formula[i].isupper():
element, frequency = formula[i], ""
while i + 1 < n and formula[i + 1].islower():
element += formula[i + 1]
i += 1
while i + 1 < n and formula[i + 1].isnumeric():
frequency += formula[i + 1]
i += 1
stack.append(element)
stack.append(frequency if frequency else "1")
else:
stack.append(formula[i])
i += 1
freq_map = Counter()
for i in range(0, len(stack), 2):
freq_map[stack[i]] += int(stack[i + 1])
ans = ""
for c in sorted(freq_map.keys()):
if freq_map[c] == 1:
ans += c
else:
ans += c + str(freq_map[c])
return ans
I love solving problems, but today I am questioning my existence and I want to quit
bro is trolling java at this point
Java person here, neetcode should I switch to python? Where can I learn this?😊
Python is basically sudo code if you can understand the sudocode then you can code it in any language.
Edit - Sorry I did not saw the video and commented. I guess Navdeep need to avoid build-in python functions.
@@freecourseplatformenglish2829 hmm I know how to do in java, planning to switch to python after some time
Isn't this incorrect.
The problem specifically states that there will be "zero or more lowercase characters"...
Considering only two is against the problem description
I guess the desc is wrong because I can't recall any real chemistry elements with more than two characters
At 28:47, do I hear the hindi word "Accha"🤔
At 19:47 N should be 2, not 1
no 1 hours thanks
Cpp person here lol
i was doing it in js it was 79 lines
Solved it on my own. To much logic is required that makes it hard otherwise it is a medium STACK Problem.
Brave person I am, get good I will
Upvote for Science👍👍
i love you man
Python solution - 28 lines:
class Solution:
def countOfAtoms(self, formula: str) -> str:
atoms, element = defaultdict(int), deque()
count, stack = deque(), ["1"]
for character in reversed(formula):
if character.isnumeric():
count.appendleft(character)
elif character == ")":
count.appendleft("0")
stack.append(max(1, int("".join(count))) * int(stack[-1]))
count.clear()
elif character == "(":
stack.pop()
count.clear()
elif character.islower():
element.appendleft(character)
else:
element.appendleft(character)
count.appendleft("0")
atoms["".join(element)] += max(1, int("".join(count))) * int(stack[-1])
element.clear()
count.clear()
return "".join(
[
f"{element}{count}" if count > 1 else element
for element, count in sorted(atoms.items())
]
)
who's here after solving this question looking for an alternate approach
if this question comes in your interview that means they don't want to hire you
this looks like a promotional video of python 😂😂😂
Longer Video ++
implement 1 hour video
bro I am using Java, and I am understand most of the codes, but if there is a part I cannot understand, I will just call chatgpt to translate lol
Would hope such question never comes in interview.
I solved it using a queue in a bfs fashion.
Hahaha let’s translate that
I solved this in 50 lines of python code :(
Java coders watching this
First view and comment 😂
Stack of HashMaps. Seriously?
28:
class Solution:
def countOfAtoms(self, f: str) -> str:
s,l,p=[],len(f:='('+f+')'),0
while p
hello bro plz try to keep the solutions within 20 mins plz so that our concentration levels are high through out
shutyo ass
Give me 1% of your property
wtf!! i did not solved the question yet but approach to solve this question is very simple. why the fuck this video is 33min long. what am i missing ??
I did this solution in rust. Before watching this, 110 lines of code and it's the O^2 solution.
pub struct Solution;
#[derive(Debug)]
struct Atom {
quantity: i32,
symbol: String,
}
#[derive(Debug)]
enum FormulaPiece {
Atom(Atom),
OpenParenthesis,
CloseParenthesis(i32),
}
use std::collections::HashMap;
use FormulaPiece::*;
impl Solution {
pub fn count_of_atoms(formula: String) -> String {
let mut new_formula: Vec = vec![];
let mut prev_nums: Vec = vec![];
let mut prev_letters: Vec = vec![];
fn insert_atom(
new_formula: &mut Vec,
prev_nums: &mut Vec,
prev_letters: &mut Vec,
) {
if prev_letters.len() > 0 {
let symbol: String = prev_letters.iter().collect();
let quantity = if prev_nums.len() == 0 {
1
} else {
prev_nums.iter().fold(0, |prev, cur| prev * 10 + cur)
};
new_formula.push(Atom(Atom { quantity, symbol }));
prev_letters.clear();
prev_nums.clear();
}
if prev_nums.len() > 0 {
if let Some(CloseParenthesis(_)) = new_formula.last() {
new_formula.pop();
new_formula.push(CloseParenthesis(
prev_nums.iter().fold(0, |prev, cur| prev * 10 + cur),
));
prev_nums.clear();
}
}
}
for c in formula.chars() {
match c {
'(' => {
insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters);
new_formula.push(OpenParenthesis);
}
')' => {
insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters);
new_formula.push(CloseParenthesis(1));
}
'0'..='9' => prev_nums.push(c.to_digit(10).unwrap() as i32),
'A'..='Z' => {
//if it's uppercase then I know that it's a new thing.
insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters);
prev_letters.push(c);
}
'a'..='z' => prev_letters.push(c),
_ => panic!("Should not happen"),
}
}
insert_atom(&mut new_formula, &mut prev_nums, &mut prev_letters);
let mut stack: Vec = vec![];
for form in new_formula {
if let CloseParenthesis(num) = form {
let mut new_stack = vec![];
while let Some(f) = stack.pop() {
match f {
OpenParenthesis => break,
FormulaPiece::Atom(Atom { quantity, symbol }) => {
new_stack.push(Atom(Atom {
quantity: quantity * num,
symbol,
}))
}
_ => panic!("should not happen"),
}
}
stack.extend(new_stack.into_iter());
} else {
stack.push(form);
}
}
let mut map: HashMap = HashMap::new();
for atm in stack {
if let Atom(Atom { quantity, symbol }) = atm {
*map.entry(symbol).or_insert(0) += quantity;
}
}
let mut tup_elements: Vec = map.into_iter().collect();
tup_elements.sort_unstable();
tup_elements
.into_iter()
.map(|(mut key, qtd)| {
if qtd > 1 {
key.push_str(qtd.to_string().as_str());
}
key
})
.collect()
}
}
class Solution {
public:
string countOfAtoms(string s) {
int multiplier = 1;
stack st1;
map mpp;
int n = s.size();
string t = "";
for(int i=n-1;i>=0;i--){
if(s[i] ='0'){
while(s[i]='0'){
t = s[i] + t;
i--;
}
i++;
int m = stoi(t);
multiplier*=m;
st1.push(m);
}
else if(s[i] == ')'){
t = "";
}
else if(s[i] == '('){
if(!st1.empty()){
multiplier/=st1.top();
st1.pop();
}
}
else{
int m = 0;
string p = "";
if(t == ""){
m=1;
}
if(s[i]='A'){
p+=s[i];
}else{
p = s[i-1];
p+=s[i];
i--;
}
mpp[p]+=multiplier;
if(t!=""){
if(!st1.empty()){
multiplier/=st1.top();
st1.pop();
}
}
t="";
}
}
string ans = "";
for(auto it: mpp){
if(it.second!=0){
ans+=it.first;
if(it.second > 1){
ans+=to_string(it.second);
}
}
}
//cout