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

Rhythm Jain
Last Updated: May 13, 2022

Introduction

String questions are increasingly becoming popular among interview questions. Therefore it is necessary to master questions based on string applications to ace technical interviews of big companies.

So Today, we will discuss a problem based on the String and Its applications.

Problem Statement

You are given a string S consisting of N digits. You aim to find the minimum length of string that can be formed after removing all the adjacent consecutive characters arranged in either increasing or decreasing order.

Example

Input:

S = “12213”

Output:

1

Explanation

Since substring ( S[0]: S[1] ) is in increasing order so remove it. The string becomes “213”. Now again, removing ( S[0]: S[1] ) because it’s decreasing consecutively. The new string becomes “3”. So the length of the string is 1.

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;
}

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.

Frequently Asked Questions

  1. 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).
     
  2. 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.

Key Takeaways

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

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think