trang chủ / bài tập / balsubstr

Xâu con cân bằng

Đề bài

Mô tả

Cho một xâu nhị phân s độ dài n, chỉ gồm các ký tự 0 và 1.

Xâu con liên tiếp [l,r] của s là xâu slsl+1sr, có độ dài rl+1. Một xâu con liên tiếp được gọi là cân bằng nếu số ký tự 0 trong nó bằng đúng số ký tự 1.

Hãy tìm độ dài lớn nhất của một xâu con liên tiếp cân bằng của s. Nếu s không có xâu con liên tiếp cân bằng khác rỗng nào, kết quả là 0.

Dữ liệu vào

  • Dòng thứ nhất chứa số nguyên n: độ dài của xâu s.
  • Dòng thứ hai chứa xâu s gồm đúng n ký tự, mỗi ký tự là 0 hoặc 1.

Dữ liệu ra

Một số nguyên duy nhất: độ dài lớn nhất của một xâu con liên tiếp cân bằng của s, hoặc 0 nếu không tồn tại.

Ràng buộc

  • 1n100000
  • s chỉ gồm các ký tự 0 và 1

Ví dụ

Input Output Giải thích
8
11010111
4 Xâu con [3,6] là 0101, có 2 số 0 và 2 số 1 nên cân bằng, độ dài 4. Xâu con [2,5] = 1010 cũng cho kết quả tương tự. Không có xâu con cân bằng nào dài hơn.
3
111
0 Xâu không chứa ký tự 0 nào nên mọi xâu con khác rỗng đều không cân bằng.
10
0011011111
6 Xâu con [1,6] = 001101 có 3 số 0 và 3 số 1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0