Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Approach
3.
3.1.
What is a Stack?
3.2.
Why are we using StringBuilder instead of a String in the code?
3.3.
What is the Time complexity of the approach used to minimize a binary string?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

# Minimize a Binary String by Repeatedly Removing Even-Length Substrings of the Same Characters

Nishant Rana
1 upvote

## 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.

1. We will start iterating the String from index â€˜0â€™ till â€˜N - 1â€™.
2. If the stack is empty, we will push the current character in the stack.
3. 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.
4. 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.
*/
}

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++

## Frequently Asked Questions

### What is a Stack?

A stack is a data structure in which we can add and remove the data only from the top. It follows the Last In First Out property stating the element which is inserted last gets removed first. This property helped us to solve this question.

### Why are we using StringBuilder instead of a String in the code?

StringBuilder is mutable in nature. Hence, if we append a character at the end, it will take O(1) time. Whereas Strings are immutable in nature and take O(N) time when we append a character at the end of it.

### What is the Time complexity of the approach used to minimize a binary string?

The time complexity of the approach used to minimize a binary string is O(N) (where N is the length of the String) because we are iterating the String only once.

## Conclusion

In this blog, we have covered the following things related to minimizing a binary string by repeatedly removing even-length substrings of the same characters:

1. We first discussed the Stack approach to minimize a binary string.
2. Then we discussed the time and space complexity of the approach used to minimize a binary string.

Recommended problems -

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.