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.
1public class MinLength {
2 public static int minLengthAfterRemovals(String s) {
3 char[] arr = s.toCharArray();
4 int write = 0;
5 for (int read = 0; read < s.length(); read++) {
6 if (write > 0 && ((arr[read] == 'B' && arr[write - 1] == 'A') || (arr[read] == 'D' && arr[write - 1] == 'C'))) {
7 write--;
8 } else {
9 arr[write++] = arr[read];
10 }
11 }
12 return write;
13 }
14
15 public static void main(String[] args) {
16 String s = "ABFCACDB";
17 System.out.println(minLengthAfterRemovals(s));
18 }
19}This Java solution translates the two-pointer logic into Java by deconstructing the input to a character array. This allows direct manipulation similar to C-style string approaches, achieving an in-place modification.