Questions
========================================


Decode String
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Given an encoded string, return it's decoded string.

The encoding rule is: `k[encoded_string]`, where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like `3a` or `2[4]`.

Examples:

.. code-block:: text

    input: "3[a]2[bc]", output: "aaabcbc".
    input: "3[a2[c]]", output: "accaccacc".
    input: "2[abc]3[cd]ef", output: "abcabccdcdcdef".



.. only:: html
   
   `leetcode <https://leetcode.com/problems/decode-string/>`_


The original problem and its subproblem have the same structure, so this problem can be easily done with a recursive function or DFS. It is very important to clearly define the input and output of the recursive function. In this case, the output is the resulting string from square bracket pair `[...]`, and the input is the original string and index. We can write code like:


.. code-block:: c++
    :linenos:

    struct Solution {
        string decodeString(string s) {
            int i = 0;
            return rec(s, i);
        }
        string rec(string& s, int& i) {
            string r; // final result
            int m = 0; // multiplier
            for (; i<s.size(); i++) {
                if (isalpha(s[i]))
                    r += s[i];
                else if (isdigit(s[i]))
                    m = m * 10 + s[i] - '0';
                else if (s[i] == '[') {
                    i++;////
                    string t = rec(s, i);
                    while (m) r += t, m--;
                } else if (s[i] == ']')
                    return r;////
            }
            return r;
        }
    };


The input also has a parenthesis structure(ref to:`CLRS page 606`). DFS is actually a recursive algorithm.

Shortest Length of Folding String
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Given a string and folding rule, find the length of its shortest fold.

The folding rule is:

.. code-block:: text

    1. A string can be regarded as its own fold. Denoted as S ~ S
    2. X(S) is a fold of a string of X(X>1) Ss connected together. Denoted as X(S) ~ SSSS...S(X S).
    3. If A ~ A', B ~ B', then AB ~ A'B'.
       For example, because 3(A) = AAA, 2(B) = BB, so 3(A)C2(B) ~ AAACBB, and 2(3(A)C)2(B) ~ AAACAAACBB

For example, the shortest fold of AAAAAAAAAABABABCCCD is: 9(A)3(AB)CCD.

Example:

.. code-block:: text

    input: "NEERCYESYESYESNEERCYESYESYES", output: 14.
    Explanation: A shortest fold is: 2(NEERC3(YES)) and length of string 2(NEERC3(YES)) is 14.


----


`dp[l][r]` to denote the shortest fold length of `s[l:r]`

There is formula:

.. code-block:: text

    dp[l][r] = min(r-l+1, dp[l][k] + dp[k+1][r]) where l<=k<r


But there is a edge case will make this formula fail. If s is a string with 10 repeated `abc`, then `abc9(abc)` and `9(abc)abc` will be the solution, which is wrong. To fix this, we need to consider the case when `[k+1][r]` can be derived from repeating `[l][k]`:

.. code-block:: text

    dp[l][r]=min(dp[l][r],dp[l][k]+2+IntLen((r-l+1)/(k-l+1)))；




.. literalinclude:: fold.cpp
   :language: c++
   :emphasize-lines: 13-23
   :linenos:
   :lines: 4-33



TC:`O(N^2)`, SC:`O(N^2)`

This is a top-down DP.


.. only:: html
   
   http://hzwer.com/1905.html  Refer to: BZOJ1090, SCOI2003


Repeated Substring Pattern
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Given a string `str`, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Examples:
 
.. code-block:: text

    Input: str = "abcabcabc"
    Output: true
    The given string is 3 times repetition of "abc"

    Input: str = "abadabad"
    Output: true
    The given string is 2 times repetition of "abad"

    Input: str = "aabaabaabaab"
    Output: true
    The given string is 4 times repetition of "aab"

    Input: str = "abcdabc"
    Output: false

.. only:: html
   
   - `leetcode <https://leetcode.com/problems/repeated-substring-pattern/>`_

   - `G4G <http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/>`_


----

.. only:: html

    - Brute Force

        .. literalinclude:: repeated.cpp
            :language: c++
            :emphasize-lines: 2-12
            :linenos:
            :lines: 4-26

- LPPP (longest proper prefix and postfix)


Longest Palindromic Prefix
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

.. code-block:: text

    Input: s = "aacecaaa", Output: "aaacecaaa"
    Input: s = "abcd", Output: "dcbabcd"

----

.. only:: html

    - Brute Force (T:`O(N^2)`, SC:`O(1)`)

        .. literalinclude:: lpp.cpp
            :language: c++
            :emphasize-lines: 2-7
            :linenos:
            :lines: 3-21

- Rolling Hash (T:`O(N)`, SC:`O(1)`)

.. literalinclude:: lpp.cpp
    :language: c++
    :emphasize-lines: 8-11
    :linenos:
    :lines: 21-35


|:bulb:|



Guess Word
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

给一个target单词，一个guess单词，如果位置完全匹配是G，字母匹配但是位置不匹配是Y，否则是R。如果有多个可以匹配为Y的，则把index最小的匹配成Y，其他的还是R，然后输出结果的string。
比如BACD和CAGE，就输出YGRR。

follow up是如果给一个target和a sequence of guess words，每一步要求前一步的guess是G的地方需要retain，前一步如果是Y的corresponding letter must be included in这个单词。输出这sequence of guess words是不是全部valid.

比如说我的target是ABCDE, 我有一个guess word的序列，The first guess word是AGHBD，那么第一步得到的结果就是GRRYY，
下一步的话valid的guess就可以是比如ACBDG（G的位置必须index和值都还是原来的，所以第一个位置必须是A，Y的地方必需至少包含，所以必须包含BD），像AGHYU或者BDAHG就不行
给一个guess word的list，判断是不是每次猜测都是基于前一步的guess的valid guess

.. code-block:: text

    Example:
    target: ABCDE, guess words: {"AGHBD","ACBDG","AFBDC","ABCDE"}, output: true
    target: ABCDE, guess words: {"AGHBD","AGHYU"}, output: false
    target: ABCDE, guess words: {"AGHBD","BDAHG"}, output: false

----

.. literalinclude:: code/guess_word_test.cpp
    :language: c++
    :linenos:

.. only:: html

  - https://www.1point3acres.com/bbs/thread-896429-1-1.html
  - https://www.1point3acres.com/bbs/thread-898295-1-1.html