Shortest String Solution | JULY 2021 CODING MARATHON

Shortest String

You are given a string containing only ‘1’ and ‘0’. You can delete either the “10” or “00” substring from the string and after deletion, the remaining string gets concatenated. Find the length of the shortest string that you can make by performing the above operation any number of times.

Input Format

The first line contains a single integer TT – the number of test cases. The first and only line of each test case contains a non-empty string that contains only ‘1’ and ‘0’.

Output Format

For each test case, print a single integer – the length of the shortest string that you can make.

Constraints

1≤T≤2∗1021≤T≤2∗102 1≤|S|≤2∗1051≤|S|≤2∗105 |S||S| is the length of the string.

Time Limit

1 second

Example

Sample Input

2 111 0101

Sample Output

3 2

Sample test case Explanation

In the first test case, you can’t delete anything. In the second test case delete “10” to get “01” as the shortest string of length 22.

Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.

JULY 2021 CODING MARATHON

Leave a Comment