做的时候一直在想是不是动态规划或者分治之类的问题，交卷后看了题解才知道是括号匹配的变形。
既然数字只有6和9，就不需要用堆栈了，只需要一个变量cnt记录未匹配的6的数量

思路

根据题目对于69匹配序列的定义可以看出：

• 对于一个合法的69序列，6和9的数量一定是相等的，即一个6对应一个9
• 6和9不仅一一对应，并且每一对69中的6都在9之前

因此可以采用以下步骤：

• 用一个变量cnt记录待匹配的6的数量，初始值为0；用ret代表要返回的字符串，即最终的结果
• 接下来依次遍历S中的字符
• 如果遇到6，就将cnt加一
• 如果遇到9，需要判断cnt是否为0
  • 如果此时cnt == 0，说明S的左侧缺了一个6，因此在ret中加上一个6
  • 否则，cnt直接减一即可，代表配对成功
• 遍历完毕之后，如果cnt不为0，说明S的右侧缺了cnt个9，因此ret = ret + S + cnt个9

复杂度分析

只需要遍历一次，因此复杂度是O(N)

C++实现

class Solution 
{
public:
    string Paired69(string S)
    {
        string ret;
        int cnt = 0;
        for (auto c : S)
        {
            if (c == '6')
            {
                cnt++;
            }
            else
            {
                if (cnt == 0)
                    ret.push_back('6');
                else
                    cnt--;
            }
        }
        ret += S;
        for (int i = 0; i < cnt; ++i)
            ret.push_back('9');
        return ret;
    }
};