| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Somebody help me with this problem. How to get all the permutations of pop and push operations? as there are no constraints specified I think checking all the permutation by brute force will get me TLE, so is there any good approach to solve this problem?
Note that two anagram strings are equal when sorted. Note also that each sequence of "push" and "pop" operations for a string of length $$$n$$$ is composed of balanced arrangement of $$$n$$$ "push" operations and $$$n$$$ "pop" operation such that no "pop" operation is done when the stack is empty. In other words, the only valid operation when the stack is empty is "push". It also follows that the first operation in any valid sequence is "push", and that the last operation in any valid sequence is "pop". Finally, note that "pop" is valid only if the letter on top of the stack is equal to the next letter in the target string. It follows from these constraints that it is not necessary to generate all possible $$$2n!$$$ full permutations of $$$n$$$ "push" and $$$n$$$ "pop" operations, and that a candidate prefix of the possible sequence can be pruned as soon as it is invalid with respect to target string and with respect to the present state of stack regardless of any used postfix.
Like in conversion from madam to adamm we have to keep track of the frequency of each letter in a map,, ?? cause for adamm we need 1st char a and a comes twice in the string at pos. 2 and 4 so either we can push consecutively 2 times or 4 times in a row. Is that correct?
We do not have to use a map to keep track of the frequency of each letter. But if we do, both maps for the source word and the destination word have to be equal. Let us assume that both words are anagram, i.e. they have the same number of letters $$$n$$$ and the same frequency for each existing letter. Let us assume that we have two pointer $$$i$$$ and $$$o$$$ that denote the position in the source word and destination word to be pushed to the stack and to be popped from the stack, respectively. Initially, $$$i = o = 0$$$ and the stack is empty. There are two different cases. The first case is when $$$i < n$$$, the present letter src[i] can be pushed to the stack, and $$$i$$$ is incremented. The second case is when $$$o < n$$$, the stack is not empty and dest[o] is equal to the top of the stack, then top of the stack can be popped from the stack, and $$$o$$$ is incremented. The final state is reached when $$$i = o = n$$$. This is a decision tree in which each "push" or "pop" choice is an edge in the tree, and non-leaf nodes have one or two children nodes, and the leaf nodes where the final state is reached represent a valid sequence. Each valid sequence is this tree is a path from the root node to a leaf node where the edges are marked with either "push" or "pop".
backtracking.