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.
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 worstcase 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:
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!