Loading...
Loading...
Loading...
A placement cell logs each mock interview with a digit: 0 for not selected, 1 for waitlisted and 2 for selected. The log has n digits in order.
Find the longest stretch of consecutive entries that has the same number of 0s, 1s and 2s. Print its length, or 0 if there is no such stretch.
0, 1 or 2.0.Example 1
Input
7 0102010
Output
3
Entries 2–4 (102) and entries 4–6 (201) are balanced. Neither stretch of length 6 is: both have three 0s.
Example 2
Input
3 000
Output
0
There are no 1s or 2s, so no stretch is balanced.
Try the problem first. Open one hint at a time.
A stretch is balanced when its 0s, 1s and 2s are equal. Two numbers capture that: (1s − 0s) and (2s − 1s) inside the stretch.
Track running counts c0, c1, c2. If the pair (c1 − c0, c2 − c1) after entry j equals the pair after an earlier entry i, then entries i + 1 to j are balanced.
Use the pair as a HashMap key, such as the string d1 + "," + d2, and store the first entry where each pair appears.
Store the pair (0, 0) at entry 0 before you start, so stretches that begin at entry 1 are found.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor