<p>Given an encoded string, return its decoded string.</p>

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

<p>You may assume that the input string is always valid; there are 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, <code>k</code>. For example, there will not be input like <code>3a</code> or <code>2[4]</code>.</p>

<p>The test cases are generated so that the length of the output will never exceed <code>10<sup>5</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;3[a]2[bc]&quot;
<strong>Output:</strong> &quot;aaabcbc&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;3[a2[c]]&quot;
<strong>Output:</strong> &quot;accaccacc&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;2[abc]3[cd]ef&quot;
<strong>Output:</strong> &quot;abcabccdcdcdef&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 30</code></li>
	<li><code>s</code> consists of lowercase English letters, digits, and square brackets <code>&#39;[]&#39;</code>.</li>
	<li><code>s</code> is guaranteed to be <strong>a valid</strong> input.</li>
	<li>All the integers in <code>s</code> are in the range <code>[1, 300]</code>.</li>
</ul>

constexpr size_t npos = -1;

pair<char,size_t> invalid = {'/',npos};

template<typename T>
bool is_invalid(const pair<T,size_t> ans)
{
    return ans.second==npos;
}

pair<char, size_t> try_parse_char(const string& str, size_t i,char c){
    if(i>=str.size()) return invalid;
    if(c!=str[i]) return invalid;
    return {c,i+1};
}

pair<char, size_t> try_parse_letter(const string& str, size_t i){
    if(i>=str.size()) return invalid;
    auto curr = str[i];
    if(curr>='a'&&curr<='z') return {curr,i+1};
    return invalid;
}

pair<string,size_t> try_parse_letters(const string& str, size_t i){
    string curr = "";
    size_t j=i;
    for(;j<str.length();)
    {
        auto ans = try_parse_letter(str,j);
        if(ans.second==npos) break;
        curr+=ans.first;
        j=ans.second;
    }
    if(curr=="") return {"",npos};
    return {curr,j};
}

pair<char,size_t> try_parse_digit(const string& str, size_t i){
    if(i>=str.size()) return invalid;
    auto curr = str[i];
    if(curr>='0'&&curr<='9') return {curr,i+1};
    return invalid;
}

pair<int,size_t> try_parse_number(const string& str, size_t i){
    string curr = "";
    size_t j=i;
    for(;j<str.length();)
    {
        auto ans = try_parse_digit(str,j);
        if(ans.second==-1) break;
        curr+=ans.first;
        j=ans.second;
    }
    if(curr=="") return {0,npos};
    return {stoi(curr),j};
}

pair<string,size_t> try_parse_code(const string& str, size_t i);

pair<string,size_t> try_parse_pattern(const string& str, size_t i){
    auto number = try_parse_number(str,i);
    if(number.second==npos) return {"",npos};
    
    auto bracket_start = try_parse_char(str,number.second,'[');
    if(is_invalid(bracket_start)) return {"",npos};
    
    auto code = try_parse_code(str,bracket_start.second);
    if(is_invalid(code)) return {"",npos};
    
    auto bracket_end = try_parse_char(str,code.second,']');
    if(is_invalid(bracket_end)) return {"",npos};
    
    string result="";
    for(auto k=number.first;k>0;k--){
        result+=code.first;
    }
    return {result,bracket_end.second};
}

pair<string,size_t> try_parse_code(const string& str, size_t i){
    string curr = "";
    size_t j=i;
    for(;j<str.length();)
    {
        auto ans = try_parse_pattern(str,j);
        if(is_invalid(ans))
            ans = try_parse_letters(str,j);
        if(is_invalid(ans))
            break;
        curr+=ans.first;
        j=ans.second;
    }
    if(curr=="") return {"",npos};
    return {curr,j};
}
    



class Solution {
public:
    string decodeString(string s) {
        auto ans = try_parse_code(s,0);
        return ans.first;
    }
};
8500