EMTY2 - Can You Make It Empty 2

You are given a string S with only 0 and 1. You can delete the string 100 from any position of S an infinite number of times and obtain a new S after concatenation. Is it possible to make the string empty?

As for example, if S=101000 then 101000->100->empty

If S=1010001 then 1010001->1001->1->not empty


Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a string S. The size of string is at most 120000.


For each test case, print the case number and “yes” if it is possible to make the string S empty, print “no” otherwise.

Sample Input

Output for Sample Input


Case 1: yes
Case 2: no

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology

hide comments
dwij28: 2016-10-16 22:50:20

Standard Problem on Stacks.

Anushka: 2016-07-03 14:16:09

There is a space after ':'.. Costed me a useless WA

rishabh_1997: 2016-06-13 23:53:24

For those getting tle using stack, change your stack approach to the vector approach. Although such problems are always solved using stack, but it worked for me. Popping the elements can be replaced by a similar approach in vectors. :-)

ajay_5097: 2016-05-17 16:10:08

Easy one - O(n) !!
AC in 1st attempt!!!

Last edit: 2016-05-17 16:11:15
aakash_s: 2015-12-22 15:53:51

Trying to do it using stack ...can anyone provide me with testcases....can't understand what went wrong

Aditya Kumar: 2015-09-25 16:14:41

Its direct!! O(N)

gaurav117: 2015-08-11 13:32:27

Finally my 50th...... ;)

Vipul Srivastava: 2015-06-10 17:17:50

there is a 'space' after ':' got many WA due to this

BRAIN: 2015-06-08 14:58:06

O(n) :"> 0.00s

BRAIN: 2015-06-08 14:36:09

O(nlog(n)) n = length of string @@!!

Added by:Md Abdul Alim
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem