Sponsored
Sponsored
This approach revolves around using a stack to efficiently identify and remove the substrings "AB" and "CD" from the given string. By traversing each character of the string:
The characters that remain on the stack are the ones that could not form any removable patterns, thus forming the result string.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), to store the stack elements, based on the worst case where no pairs are removed.
1#include <iostream>
2#include <stack>
3using namespace std;
4
5int minLengthAfterRemovals(string s) {
6 stack<char> st;
7 for (char c : s) {
8 if (!st.empty() && ((c == 'B' && st.top() == 'A') || (c == 'D' && st.top() == 'C'))) {
9 st.pop();
10 } else {
11 st.push(c);
12 }
13 }
14 return st.size();
}
int main() {
string s = "ABFCACDB";
cout << minLengthAfterRemovals(s) << endl;
return 0;
}This C++ solution uses the standard stack from the STL to manage the stack operations. We iterate through the string and apply push/pop operations based on matching conditions.
This technique uses a two-pointer approach to reduce the string by altering it in place. The core idea is to selectively overwrite positions in the string:
After reaching the end of the string, the length of the string from the start to the write pointer represents the reduced string length.
Time Complexity: O(n), dependent on examining each character once.
Space Complexity: O(1), as no additional data structures are used.
1#include <stdio.h>
2#include <string.h>
3
4int minLengthAfterRemovals(char *s) {
5 int n = strlen(s);
6 int write = 0;
7 for (int read = 0; read < n; ++read) {
8 if (write && ((s[read] == 'B' && s[write - 1] == 'A') || (s[read] == 'D' && s[write - 1] == 'C'))) {
9 --write;
10 } else {
11 s[write++] = s[read];
12 }
13 }
14 return write;
15}
16
17int main() {
18 char s[] = "ABFCACDB";
19 printf("%d\n", minLengthAfterRemovals(s));
20 return 0;
21}This method involves editing the string in place. With two pointers ('read' and 'write'), we adjust the string as we progress. The write pointer helps track the new end of the string by overwriting unnecessary characters.