Find the minimum number of operations to make Binary String Empty

Problem Statement:You are given a binary string( a string of 0 and 1) 's' of length N.

You want to convert s into an empty string by performing the following operations least number of times.

-> In one operation, you can remove an Alternating Subsequence  from S without changing the order of remaining characters.

Your task is to determine the minimum number of operations required to convert s into an empty string.

input:N=10 

S=0100100111  

Output:3  

Explanation:1)Remove subsequence '010101' from 0100100111 to make it 0011 2)Remove 01 from 0011 to make it 01 3)finally remove 01 to make it an empty string. 

input:N=4 S=1111  

Output:4 

Explantion:Remove individual 1 four times

Approach:We can easily solve this problem by Creating Two array of size n.In array 1 we will keep count of 1 that has occured up to i-th position & in array 2 we will keep the count of 0 that has occured up to i-th position.

for ex-in the above 1st test case S=0100100111,

array 1 will be-0111222345

array 2 will be-1123345555

if suppose at ith position the length of string is odd then for string to be alternating the absolute difference between (count of 0- count of 1) upto that ith position should be 1,similarly if at ith position the length of string is even then for string to be alternating the absolute difference between(count0-count1) upto that ith position  should be 0,else answer will be (max of(a1[i]-a2[i])+max of(a2[i]-a1[i])

Below is the Java implementation of the above approach:

Code

import java.io.*;

class Solution {
    public static void main(String[] args) {
        Scanner obj=new Scanner(System.in);
        int n=obj.nextInt();      // Taking input of Integer N as String
        String s=obj.next();      // Taking input of Integer K as String
       
        ArrayList<Integer> list0=new ArrayList<>();
        ArrayList<Integer> list1=new ArrayList<>();
       
        int count0=0,count1=0;
       
        for(int i=0;i<n;i++)                    //creating count of 0 array
        {
            if(s.charAt(i)=='0')
            {
                count0++;
            }
            list0.add(count0);
        }
       
        for(int i=0;i<n;i++)                        //creating count of 1 array
        {
            if(s.charAt(i)=='1')
            {
                count1++;
            }
            list1.add(count1);
        }
        int max1=0,max2=0;
        for(int i=0;i<n;i++)
        {
            max1=Math.max(max1, list0.get(i)-list1.get(i));
        }
        for(int i=0;i<n;i++)
        {
            max2=Math.max(max2, list1.get(i)-list0.get(i));
        }
        System.out.println(max1+max2);
        obj.close();
    }
}

Time Complexity-O(n) 

NOTE:This problem was asked in NASDAQ INTERN HIRING CHALLENGE

Feel free to comment if you have any doubt in comment sections

For more Data structure and algorithms,computer science,programming,coding related problems search my website.


Learn how to prepare for Information Technology Based companies here