codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

873B.md (1275B)


      1 Source: https://codeforces.com/problemset/problem/873/B
      2 
      3 B. Balanced Substring
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string *s* consisting only of characters 0 and 1. A substring [*l*, *r*] of *s* is a string *s**l**s**l* + 1*s**l* + 2... *s**r*, and its length equals to *r* - *l* + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.
     22 
     23 You have to determine the length of the longest balanced substring of *s*.
     24 
     25 Input
     26 
     27 The first line contains *n* (1 ≤ *n* ≤ 100000) — the number of characters in *s*.
     28 
     29 The second line contains a string *s* consisting of exactly *n* characters. Only characters 0 and 1 can appear in *s*.
     30 
     31 Output
     32 
     33 If there is no non-empty balanced substring in *s*, print 0. Otherwise, print the length of the longest balanced substring.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 8  
     41 11010111
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 4
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 3  
     54 111
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 0
     61 ```
     62 
     63 Note
     64 
     65 In the first example you can choose the substring [3, 6]. It is balanced, and its length is 4. Choosing the substring [2, 5] is also possible.
     66 
     67 In the second example it's impossible to find a non-empty balanced substring.