Odd Versus Even in a Window

Hard

You are given a string digits made of the digits 0 to 4, and an integer min_len. Pick a substring (a contiguous piece) of length at least min_len and two different digits a and b such that, inside that substring: - digit a occurs an **odd** number of times; - digit b occurs an **even** number of times, and at least twice (so it is actually present). Other digits may occur in the substring any number of times. Return the largest possible value of count(a) - count(b) over all such choices. The answer may be negative.

Example 1

digits="3011", min_len=3 → -1

In the substring "011", digit 0 occurs once (odd) and 1 twice (even): 1 - 2 = -1. Nothing does better.

Example 2

digits="2224400", min_len=5 → 1

Take "22244": 2 occurs 3 times and 4 twice, so the difference is 3 - 2 = 1.

Example 3

digits="1113300", min_len=3 → 1

Constraints

3 ≤ len(digits) ≤ 3·10⁴
digits contains only the digits 0–4
1 ≤ min_len ≤ len(digits)
At least one valid choice exists

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Enumeration Prefix Sum Sliding Window

Similar problems

Few Zeros or Few Ones: Range Queries Hard Matching Stretch Within Budget Medium Hop Across Safe Tiles Medium Longest Uniform Answer Run Medium Even Vowel and Consonant Pieces Medium

Input

digits="3011", min_len=3

Expected

-1

Run checks the first 3 tests in your browser. Submit checks all 108 tests on the server, hidden ones included.