Longest Even Length Substring Sum

mediumSave

Prefix SumString

Given a string consisting of digits (0-9), find the length of the longest contiguous substring that is even in length and whose first half and second half have equal sum.

Example 1

Input

[
  "123123"
]

Output

Explanation. The entire string meets the conditions, with halves '123' and '123' having the same sum of 6.

Example 2

Input

[
  "1538023"
]

Output

Explanation. The longest substring that meets the condition is '5380' with halves '53' and '80' both having the sum of 8.

Example 3

Input

[
  "123456"
]

Output

Explanation. The only substring meeting the condition is generated by any two consecutive same digits.

Example 4

Input

[
  "1122"
]

Output

Explanation. The entire string meets the conditions, with halves '11' and '22' having the same sum of 2.

Example 5

Input

[
  "000000"
]

Output

Explanation. The entire string meets the conditions, with any split having the same sum of 0.

Example 6

Input

[
  "1234"
]

Output

Explanation. No even length substrings have equal halves in sums.

Follow-up: Can you optimize your solution to run in \(O(n^2)\) time complexity?

Constraints:

The input string will not be empty and will contain only digits from \(0-9\).

Views: 3