对称子字符串

Description

Given a string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits.

（给定字符串，只包含数组，找出最长的子字符串，满足子字符串的长度为2k位，左k位的总和等于右k位的总和。）

思路

遍历每一个字符x， 计算以x为中心的最长的满足条件的子字符串：

1. k从1开始，计算x左边k位和suml，与右边k位和sumr,

2. 如果相等，检查k+1，

3. 否则更新最长结果 ans = max(ans, 2*k)

参考实现（O(n^2)）

def solve(s):
    nums = list(map(int, s))
    ans, n = 0, len(nums)
    for i in range(len(nums)-1):
        l, r = i, i+1
        suml = sumr = 0
        while l >= 0 and r < n:
            suml += nums[l]
            sumr += nums[r]
            if suml == sumr and i-l+1 > ans:
                ans = i-l+1
            l -= 1
            r += 1
    return ans*2

for _ in range(int(input())):
    s = input()
    print(solve(s))

完整代码

O_NJU_JK