Coding 【每日一题】最长 AB 子串 -Python-20211013

Jack · 2021年10月13日 · 最后由 Jack 回复于 2021年10月14日 · 13 次阅读
本帖已被设为精华帖!
  1. 问题描述: 给出一个只由字母 A 和 B 组成的字符串 S,找出最长的一个子串,要求这个子串里面 A 与 B 的数目相等,输出该子串的长度。
  2. 问题示例: S = "ABAAABBBA" , 输出 8 S = "AAAAAA" , 输出 0
Jack 将本帖设为了精华贴 10月13日 21:24

参考代码:

class Solution:
    def getAns(self, S):
        ans = 0
        arr = [ 0 for i in range(len(S))]
        sets = {}
        if S[0] == 'A':
            arr[0] = 0
            sets[1] = 1
        else:
            arr[0] = -1
            sets[-1] = 0
        for i in range(1, len(S)):
            if S[i] == 'A':
                arr[i] = arr[i - 1] + 1
                if arr[i] == 0:
                    ans = i + 1
                    continue
                if arr[i] in sets:
                    ans = max(ans, i - sets[arr[i]])
                else:
                    sets[arr[i]] = i
            else:
                arr[i] = arr[i - 1] - 1
                if arr[i] == 0:
                    ans = i + 1
                    continue
                if arr[i] in sets:
                    ans = max(ans, i - sets[arr[i]])
                else:
                    sets[arr[i]] = i
        return ans
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册