Given a string S of size N consisting of characters from ‘0’to ‘9’, the task is to minimize the length of the string where In each minimizing operation, we can remove any two consecutive characters if they are of the form {“12”, “21”, “34”, “43”, “56”, “65”, “78”, “87”, “09”, “90”}.
Examples:
Input: S = “672183”
Output: 2
Explanation:
perform the minimizing operation at index 2 and 3 “672183″, after the removal resultant string will be “6783”
perform the minimizing operation at index 1 and 2 “6783″, after the removal resultant string will be”63″
Since no further minimizing operation can be performed, the minimum possible length of the string is 2.Input: S = “19532”
Output: 5
Explanation: No operation can be performed
Approach:
Traverse through the string and keep removing the consecutive characters if they are in the above-mentioned form Break if there is no pair of characters found for minimizing return of the final length of the given string
- Create a dummy string temp to store the resultant string.
- Start traversing the given string and check whether the last character forms a removable pair with the current character then remove both of them.
- To check the pairs, create another boolean function and check whether the two characters form a possible pair for minimizing operation or not.
- If yes, return true.
- Otherwise, return false.
- To check the pairs, create another boolean function and check whether the two characters form a possible pair for minimizing operation or not.
- If the size of the dummy string temp is greater than 0 and the last character and current character currChar are making pair then remove them.
- Otherwise, add the currChar in the dummy temp string.
- Return the length of the temp string.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check whether the two characters// is a possible pair for minimising operationbool checkPairs(char a, char b){ if ((a == '1' && b == '2') || (a == '2' && b == '1')) return true; else if ((a == '3' && b == '4') || (a == '4' && b == '3')) return true; else if ((a == '5' && b == '6') || (a == '6' && b == '5')) return true; else if ((a == '7' && b == '8') || (a == '8' && b == '7')) return true; else if ((a == '0' && b == '9') || (a == '9' && b == '0')) return true; return false;}// Function to check the minimum length// of the string after applying the operationint minimiseString(string& s){ // If the last character is forming // a removable pair with the current // character then remove both of them string temp = ""; for (char currChar : s) { if (temp.size() > 0 && checkPairs(temp.back(), currChar)) { temp.pop_back(); } else { temp.push_back(currChar); } } return temp.size();}// Driver Codeint main(){ string S = "672183"; // Function call cout << minimiseString(S); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Function to check whether the two character is a // possible pair for minimising operation or not private static boolean checkPairs(char a, char b) { if ((a == '1' && b == '2') || (a == '2' && b == '1')) return true; else if ((a == '3' && b == '4') || (a == '4' && b == '3')) return true; else if ((a == '5' && b == '6') || (a == '6' && b == '5')) return true; else if ((a == '7' && b == '8') || (a == '8' && b == '7')) return true; else if ((a == '0' && b == '9') || (a == '9' && b == '0')) return true; return false; } // Function to check the minimum length // of the string after applying the operation public static int minimiseString(String s) { Stack<Character> st = new Stack<>(); for (int i = 0; i < s.length(); i++) { // If the last character is // forming a removable pair // with the current character // then remove both of them if (!st.empty() && checkPairs(st.peek(), s.charAt(i))) { st.pop(); } else { st.add(s.charAt(i)); } } return st.size(); } // Driver Code public static void main(String[] args) { String S = "672183"; // Function call System.out.println(minimiseString(S)); }} |
Python3
# Python code to implement the approach# Function to check whether the two characters# is a possible pair for minimising operationdef checkPairs(a,b): if((a == '1' and b == '2') or (a == '2' and b == '1')): return True elif((a == '3' and b == '4') or (a == '4' and b == '3')): return True elif((a == '5' and b == '6') or (a == '6' and b == '5')): return True elif((a == '7' and b == '8') or (a == '8' and b == '7')): return True elif((a == '0' and b == '9') or (a == '9' and b == '0')): return True return False# Function to check the minimum length# of the string after applying the operationdef minimiseString(s): # If the last character is forming # a removable pair with the current # character then remove both of them temp="" for currChar in s: if(len(temp)>0 and checkPairs(temp[len(temp)-1],currChar)): temp = temp.rstrip(temp[-1]) else: temp=temp+currChar return len(temp) # Driver CodeS="672183"# Function callprint(minimiseString(S))# This code is contributed by Pushpesh Raj. |
C#
using System;using System.Text;using System.Collections.Generic;public class GFG { // Function to check whether the two character is a // possible pair for minimising operation or not public static bool checkPairs(char a, char b) { if ((a == '1' && b == '2') || (a == '2' && b == '1')) return true; else if ((a == '3' && b == '4') || (a == '4' && b == '3')) return true; else if ((a == '5' && b == '6') || (a == '6' && b == '5')) return true; else if ((a == '7' && b == '8') || (a == '8' && b == '7')) return true; else if ((a == '0' && b == '9') || (a == '9' && b == '0')) return true; return false; } // Function to check the minimum length // of the string after applying the operation public static int minimiseString(string s) { Stack<char> st = new Stack<char>(); for (int i = 0; i < s.Length; i++) { // If the last character is // forming a removable pair // with the current character // then remove both of them if (st.Count != 0 && checkPairs(st.Peek(), s[i])) { st.Pop(); } else { st.Push(s[i]); } } return st.Count; } // Driver Code static public void Main() { string S = "672183"; // Function call Console.WriteLine(minimiseString(S)); }}// This code is contributed by Rohit Pradhan |
Javascript
// JavaScript code to implement the approach// Function to check whether the two character is a// possible pair for minimising operation or notfunction checkPairs(a, b){ if ((a == '1' && b == '2') || (a == '2' && b == '1')) return true; else if ((a == '3' && b == '4') || (a == '4' && b == '3')) return true; else if ((a == '5' && b == '6') || (a == '6' && b == '5')) return true; else if ((a == '7' && b == '8') || (a == '8' && b == '7')) return true; else if ((a == '0' && b == '9') || (a == '9' && b == '0')) return true; return false;}// Function to check the minimum length// of the string after applying the operationfunction minimizeString(s){ var st = []; for(let i=0;i<s.length;i++){ // If the last character is // forming a removable pair // with the current character // then remove both of them if(st.length!=0 && checkPairs(st[st.length-1], s[i])){ st.pop(); } else{ st.push(s[i]); } } return st.length;}let S = "672183";// Function callconsole.log(minimizeString(S));// This code is contributed by lokesh. |
Output
2
Time Complexity: O(N) // since we are traversing the entire string using a for loop hence the loops run till the length of the stri
Auxiliary Space: O(N) // since we are using a stack to store the characters hence the space taken is equal to the length of the string
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
