All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Save the Kidney

Dynamic Programming, Medium


It is Valentine's Day and Rishabh's girlfriend has asked Rishabh to buy her the new iPhone 8 as a gift. Rishabh is a poor guy and doesn't have enough money to buy the iPhone, at the same time he does not want to disappoint his girlfriend. In order to keep his girlfriend happy, he decides to sell one of his kidneys to get the money for the iPhone.

Picture of Heart Kidney SAVE ME!!!

But he has a helpful friend - Viral, so he asks him for money so that he would not have to sell his kidney. Viral, being an algorithm lover agrees to give Rishabh the money only if he solves the following problem- You are given a string s made up of 0s, 1s and xs only. In place of 'x', you can fill in any single character - '0' or '1'. Print the length of a sub-string of s, such that after filling in all the xs with either '0' or '1', the number of 0s is equal to the number of 1s in that sub-string and the sub-string is of maximum length. Note that it is NOT necessary that all xs should have the same value. You can replace different xs with different values(either '1' or '0' only). If there is no such sub-string having equal number of 0s and 1s after replacing all the xs with 0 or 1, then print -1.

Since Rishabh is from EEE, he is not very good at coding and needs your help to solve the problem. Can you help him and save his kidney ?

REMEMBER: A sub-string is a contiguous part of the original string. The sub-string is itself a string.


1 <= n <= 100000

0 <= no. of x <= 9


The input consists of two lines.

The first line contains a single integer n denoting the length of the string.

The second line consists of a single string of length n, made up of 0, 1 and x only.


If a sub-string having equal number of 0s and 1s (after replacing all xs with either 0 or 1) does NOT exist, then, print -1.

Otherwise, print the maximum length of sub-string of s such that number of 0s equals the number of 1s (after replacing all xs with either 0 or 1).

Problem Author : Viral Mehta


If you replace one of the xs with 1 and the other with 0, then the sub-string from index 1 to index 6 (indexing starts from 1) has equal number of 0s and 1s.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1025 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications