Minimize Length of a String by Removing Pairs of Consecutive Increasing or Decreasing Digits

Approach: Using Stack

The above problem can be easily solved by using a stack that can help us keep track of the characters of the string encountered so far.

Algorithm:

• Initialize a stack of characters called “ stk ” that stores the characters of the given string S.
• Now, traverse the String S and, in each iteration, perform the following steps-
  • If the “stk” is empty then, push the character S[i] in the stack “stk.”
  • Else If the current character S[i] and character at the top of the stack differ by 1 then, pop the element from the stack “stk.” Else, push the character S[i] in the stack “stk.”
• Return the size of the stack “stk”.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int minLength(string S)
{
   // Initialize the stack st
   stack<char> stk;

   // Traverse the string S
   for (int i=0;i<S.length();i++) {

       // If the stack is empty
       if (stk.empty())
           stk.push(S[i]);

       // Otherwise
       else {

           // If current character and stk.top are
           // consecutive digits
           if (abs(S[i] - stk.top()) == 1)
               stk.pop();

           // Otherwise, push the
           // character ch
           else {
               stk.push(S[i]);
           }
       }
   }

   // Print the size of the stack
   return stk.size();
}

// Driver Code
int main()
{
   string S = "12213";
   cout << minLength(S);

   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

“12213”

Output:

1

Complexity Analysis

Time Complexity: O(N)

This is because we are traversing the entire string once

Space Complexity: O(N)

The algorithm requires a stack to store elements/characters of the string. So in the worst case, we would need O(N) space.
Check out this problem - Longest String Chain

Frequently Asked Questions

What is the time complexity of push() ,pop() and top() operations in stack ?

In a stack, the complexity of push(), pop(), and top() operations depends upon the implementation of the stack. For the inbuilt STL Stack, the complexity of all the three functions, push(), pop(),.” and top() is O(1).

Why the worst-case space complexity is O(N)?

In the worst case, we mean that neither of the adjacent elements in the string is in a consecutive increasing or decreasing fashion, so in that case, all of the string elements will be pushed into the stack leading to O(N) space.

Conclusion

String and application of various data structures on strings are the most critical technical and coding interview concepts.

On the other hand, Stack seems pretty simple data structure but can help us solve various problems efficiently and quickly.

Recommended Reading:

• Daily Temperatures
• Count Subarrays for every element in which they are minimum
• Count array elements having at least one smaller element on its left and right side
• Online Stock Span 
• Minimize a binary string by repeatedly removing even-length substrings of the same characters
• Minimize A String By Removing All Occurrences Of Another String
• Stack in C++ STL
• Top String Coding Interview Questions
• Count the group of Consecutive 1s in a Binary String
• Check if String is a Subsequence

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!