Cancel out the zeros and ones
You have a string of 0s and 1s. Whenever a 0 and a 1 sit side by side, as 01 or 10, you may delete the two of them; the characters on either side then close up. You may do this as many times as you like, in any order.
For each string, find the shortest length it can be brought down to.
Input
The first line holds T, the number of tests. Each test is one line holding one string of 0s and 1s.
Output
For each test, one line: the shortest length its string can reach.
- Input
3
0110
111
10100- Output
0
3
1
- Delete the 01 at the front to leave 10, then delete that.
- There is no 0 to pair with, so nothing can be deleted.
- 10100 becomes 100, then 0.
Limits
1 <= T <= 100each string holds 1 to 100000 charactersall the strings together hold at most 400000 characters
Hints
Hint 1
Every deletion removes exactly one 0 and one 1. What can never be deleted?
Hint 2
As long as both a 0 and a 1 are left, some 0 sits next to some 1. So deletions go on until only one kind is left: the answer is the difference between the two counts.
Where this was reported
- HSBC, Trainee software engineer on-campus interview, 2023 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
