Geek and Number String Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/904237fa926d79126d42c437802b04287ea9d1c8/1

(It is also the problem of the day for 23-09-2022)

Solution:

class Solution { 

    public int minLength(String s1, int n) { 

    Stack<Character>stack=new Stack<Character>();

   

    for(int i=0;i<s1.length();i++){

        if(stack.isEmpty()){

            stack.push((s1.charAt(i)));

        }

        else{

            String s="";

            s+=(stack.peek());

            s+=(s1.charAt(i));

            if(s.equals("12") || s.equals("21") || s.equals("34") || s.equals("43")|| s.equals("56") || s.equals("65")|| s.equals("78") || s.equals("87") || s.equals("90") || s.equals("09")){

                

                stack.pop();

            }

            else{

                stack.push((s1.charAt(i)));

            }

        }

    }

    return stack.size();

    }

}

Approach Used:

Here we need to find the minimum length of string possible after deletions of all the possible combinations present in the string which are equivalent to the strings stored in a given array of strings.

We will traverse the string and add each character to the stack.

While traversing we will also check whether that (stack.peek()+s.charAt(i)).equals(any string from string array)

  if yes then it means we need to delete them so 

    1. we will pop the stack. peek which deletes the top character(stack.pop())

    2. and since we did not add the incoming character to the stack so once we move ahead it will automatically be counted as deleted.

  So we need to perform only one operation ie stack.pop()

if no 

then traverse simply and push the character in the stack.

In last we will get the stack containing characters who were not able to form pairs according to the strings given in the question.

return stack.size();

Time Complexity: O(N)[GFG Time:0.8]

Space Complexity: O(N)

Auxiliary Space: O(N)[Stack is used][In the worst case all characters will be there in the stack.]

Total Test Cases:210

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"