B. Balanced Substring

Codeforces

IDCF873B

Time1000ms

Memory256MB

Difficulty—

dpimplementation

English · Original

Chinese · Translation

Formal · Original

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. You have to determine the length of the longest _balanced_ substring of _s_. ## Input The first line contains _n_ (1 ≤ _n_ ≤ 100000) — the number of characters in _s_. The second line contains a string _s_ consisting of exactly _n_ characters. Only characters _0_ and _1_ can appear in _s_. ## Output If there is no non-empty _balanced_ substring in _s_, print _0_. Otherwise, print the length of the longest _balanced_ substring. [samples] ## Note 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. In the second example it's impossible to find a non-empty _balanced_ substring.

给定一个仅由字符 _0_ 和 _1_ 组成的字符串 #cf_span[s]。字符串 #cf_span[s] 的子串 #cf_span[[l, r]] 是指字符串 #cf_span[slsl + 1sl + 2... sr]，其长度为 #cf_span[r - l + 1]。如果一个子串中零 (_0_) 的数量等于一的数量，则称该子串为 _平衡的_。你需要确定 #cf_span[s] 的最长 _平衡_ 子串的长度。第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 100000]) —— #cf_span[s] 中字符的个数。第二行包含一个恰好由 #cf_span[n] 个字符组成的字符串 #cf_span[s]。#cf_span[s] 中仅可能出现字符 _0_ 和 _1_。如果 #cf_span[s] 中不存在非空的 _平衡_ 子串，则输出 _0_。否则，输出最长 _平衡_ 子串的长度。在第一个例子中，你可以选择子串 #cf_span[[3, 6]]。它是 _平衡的_，长度为 #cf_span[4]。选择子串 #cf_span[[2, 5]] 也是可行的。在第二个例子中，无法找到任何非空的 _平衡_ 子串。 ## Input 第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 100000]) —— #cf_span[s] 中字符的个数。第二行包含一个恰好由 #cf_span[n] 个字符组成的字符串 #cf_span[s]。#cf_span[s] 中仅可能出现字符 _0_ 和 _1_。 ## Output 如果 #cf_span[s] 中不存在非空的 _平衡_ 子串，则输出 _0_。否则，输出最长 _平衡_ 子串的长度。 [samples] ## Note 在第一个例子中，你可以选择子串 #cf_span[[3, 6]]。它是 _平衡的_，长度为 #cf_span[4]。选择子串 #cf_span[[2, 5]] 也是可行的。在第二个例子中，无法找到任何非空的 _平衡_ 子串。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the string. Let $ s = s_1 s_2 \dots s_n $ be a string over $ \{0, 1\} $. For a substring $ s[l:r] = s_l s_{l+1} \dots s_r $, define its balance as: $$ \text{balance}(l, r) = (\text{count of } 1\text{s in } s[l:r]) - (\text{count of } 0\text{s in } s[l:r]) $$ A substring $ s[l:r] $ is *balanced* if $ \text{balance}(l, r) = 0 $. **Constraints** 1. $ 1 \leq n \leq 100000 $ 2. $ s_i \in \{0, 1\} $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the maximum length $ r - l + 1 $ over all substrings $ s[l:r] $ such that $ \text{balance}(l, r) = 0 $. If no such non-empty substring exists, output $ 0 $.

Samples

Input #1

8
11010111

Output #1

Input #2

3
111

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Balanced Substring",
    "description": {
      "content": "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 substr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF873B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 substr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个仅由字符 _0_ 和 _1_ 组成的字符串 #cf_span[s]。字符串 #cf_span[s] 的子串 #cf_span[[l, r]] 是指字符串 #cf_span[slsl + 1sl + 2... sr]，其长度为 #cf_span[r - l + 1]。如果一个子串中零 (_0_) 的数量等于一的数量，则称该子串为 _平衡的_。\n\n你需要确定 #cf_span[s] 的最长 _...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string over $ \\{0, 1\\} $.  \nFor a substring $ s[l:r] = s_l s_{l+1} \\dots s_r $, define its ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments