## Introduction

We are given a Binary String(contains â€˜0â€™s and â€˜1â€™s only) of length â€˜Nâ€™. We need to minimize a Binary String by repeatedly removing the even length substrings of the same character i.e. either â€˜0â€™ or â€˜1â€™.

Also see, Data Structures

**Input 1:**

1101

**Output 1:**

01

**Explanation:**

We will start to minimize a binary string. We will first remove the substring â€˜11â€™. After removing it we are left with 01. Now we canâ€™t remove any substring.

**Input 2:**

1011000

**Output 2:**

1

**Explanation: **

We will start to minimize a binary string. We will first remove the substring â€˜11â€™. After removing it we are left with 10000. Now we will remove â€˜0000â€™. After removing it we are left with 1. Now we can not remove any substring.

## Approach

We will solve this question using a Stack. Let us see how this problem can be solved using a Stack.

- We will start iterating the String from index â€˜0â€™ till â€˜N - 1â€™.
- If the stack is empty, we will push the current character in the stack.
- If the stack is not empty. We will compare the current character with the top of the stack. If both the character matches we pop from the stack else push the current character to the Stack.
- After iterating the entire String we will form our final String from the Stack from bottom to top.

Refer to the below implementation of the above approach.

```
static void minString(String s)
{
// Initializing a Stack
Stack<Character> stack = new Stack<Character>();
// Traverse the String 's'
for (int i = 0; i < s.length(); i++) {
// If Stack is empty
if (stack.isEmpty()) {
/*
Push the current
character to the
stack.
*/
stack.add(s.charAt(i));
}
else {
/*
Check if the current
character is same as
the top of the Stack.
*/
if (stack.peek() == s.charAt(i)) {
stack.pop();
}
/*
If not push the
current character
to the stack.
*/
else {
stack.push(s.charAt(i));
}
}
}
StringBuilder ret = new StringBuilder();
while(!stack.isEmpty()){
ret.append(stack.pop());
}
ret.reverse();
return ret.toString();
}
```

**Time Complexity:** The time complexity for the above approach is O(N) (where â€˜Nâ€™ is the length of the String) because we are iterating the String only once.**Space Complexity: **The space complexity for the above approach is O(N) (where â€˜Nâ€™ is the length of the String) because we are maintaining a Stack that will store the entire String in the worst case.

Also check out - __Substr C++__