Show problems as
Classic problem #3714MediumHash TableStringPrefix Sum

Longest Balanced Substring II

Real-world version: The Longest Evenly Dyed Stretch
Tracked in this browser only
Read Longest Balanced Substring II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A loom has laid down a run of dyed threads, threads spelling out the dye on each one as a, b or c.

A stretch of neighbouring threads is even when it holds as many a threads as b threads and as many b threads as c threads.

Return the number of threads in the longest even stretch, or 0 when no stretch of one thread or more is even.

Examples

Example 1

Input
threads = "abcabc"
Output
6

Two of each dye across the whole run, so the whole run is even.

Example 2

Input
threads = "cabc"
Output
3

The last three threads hold one of each dye. Taking the leading c as well would leave two c threads against one a thread.

Example 3

Input
threads = "aaabbbcc"
Output
0

The run is three a threads, three b threads and two c threads. Any stretch reaching the c threads has already swallowed all three b threads, so no stretch ever balances and nothing qualifies.

Constraints

  • 1 <= threads.length <= 10^5
  • threads holds only the characters a, b and c

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_balanced(threads: str) -> int:
Java
public int longestBalanced(String threads)

More on the same topics