华为蛇形字符串

题目描述：

输入一个字符串（不含空格）， 请寻找输入中包含所有蛇形字符串。
蛇形字符串定义：

1.蛇形字符串由连续字符对组成，其特点如下：
1.1 字符对定义：字符对由同一字母的大写和小写组成（前大后小）。如：Aa，Dd；
1.2 蛇形字符串中包含的字符对，必须是连续字母，并按照字母顺序排序。如：AaBbCc或OoPpQqRrSs；

2.从输入中寻找字符组成蛇形字符串（字符顺序不限），符合规则：
2.1 每次寻找必须是最长的蛇形字符串；
2.2 使用过的字符不能重复使用；

例： 输入SxxsrR^AaSs
正确处理过程：

Step1：SxxsrR^AaSs -> RrSs （找到两对连续字符对：Ss、Rr，可以组成蛇形字符串。另，Ss后应该是Tt，但当前字符串SxxsrR^AaSs中不包含，所以当前蛇形字符串到Ss结束。本轮查找结果是RrSs。）
Step2：xs^AaSs -> Aa
Step3：xx^Ss -> Ss
output：RrSs
              Aa
              Ss

分析

题目中可以看到一些关键信息

• 连续 最长 --> 连续子序列优化问题
• 题目给出的字符串 字符的顺序不重要 可以考虑使用hash表简化问题
• 大写字母必须紧跟小写字母 --> 为了将问题简化 我们只考虑大写字母 的子序列优化问题 取出大写字母时确保相应的小写字母必然存在即可

主要的循环过程

• 找出大小写字母同时存在的字母
  • 找不出字母了 循环结束...
• 执行子序列最优化
• 减去这一轮用掉的大小写字母

from collections import Counter


class solution:

    def snack(self, s):
        up, low = [], []
        for chr in s:
            if 'a' <= chr <= 'z':
                low.append(chr)
            if 'A' <= chr <= 'Z':
                up.append(chr)
        up = Counter(up)
        low = Counter(low)

        # 找出大小写都存在的字符
        def getUpLowChar():
            res = []
            for key in up: # 直观的写法
                if key.lower() in low:
                    res.append(key)
            return res

            #     if key.lower() not in low:
            #         up.pop(key)  # 大写字母存在 小写字母不存在 直接删掉大写字母 因为没用
            # return list(up.keys())

        # 连续子序列最优化
        def maxLen(s):
            maxEnd = s[0]  # 字符串可以合并
            res = s[0]
            for i in range(1, len(s)):
                if ord(s[i]) - ord(s[i - 1]) == 1:
                    maxEnd += s[i]  # 合并字符串
                else:
                    maxEnd = s[i]
                if len(maxEnd) > len(res):
                    res = maxEnd
            return res

        # 将本轮中用过的字母删除 包括大写字母和小写字母
        def decrease(s):
            for char in s:
                up[char] -= 1
                if up[char] == 0:
                    up.pop(char)

                char = char.lower()
                low[char] -= 1
                if low[char] == 0:
                    low.pop(char)

        res = []
        while up:
            chars = getUpLowChar() # 找出大小写字母都存在的字母
            if not chars:
                break
            chars.sort()

            # 连续子序列最优化
            out = maxLen(chars)
            res.append("".join(["{}{}".format(x, x.lower()) for x in out]))

            # 在字典中减去用掉的字母
            decrease(out)
        return res


if __name__ == '__main__':
    solu = solution()
    test = ' SwSE$3454356DD$$E#eswsxxsssAAWDxxdderfvcRFER65645hbg^^%%^UnbnvccTRChnyvcxcvVCFR'
    print(solu.snack(test))
    # ['CcDdEeFf', 'CcDdEe', 'RrSs', 'VvWw', 'Ss']