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

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.
            */
            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();
}

You can also try this code with Online Java Compiler

Run Code

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