What is the Time complexity of the approach used to

Minimize a binary string by repeatedly removing even-length substrings of the same characters

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

Input 1:

1101

Output 1:

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:

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.

FAQs:

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.

Key Takeaways:

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:

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

If you want to learn more about Stack and want to practice some questions which require you to take your basic knowledge on Stack a notch higher, then you can visit our Guided Path for Stack. To practice this problem, you can visit Practice Problem.

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