Minimum String Length After Removing Substrings

Leetcode Problem:

• Minimum String Length After Removing Substrings

Summary

• Given a string of uppercase English letters, find the minimum possible length of the resulting string after removing any occurrences of the substrings "AB" or "CD".

Approach

• This problem is solved using a recursive approach where we try to remove the first occurrence of "AB" or "CD" from the string and then check if the resulting string can be further reduced
• If not, we return the current minimum length.

Complexity

• O(2^n) due to the recursive calls, where n is the length of the input string.

Explanation

• The solution starts by initializing the minimum length to the length of the input string
• Then, it iterates over the string and checks for the first occurrence of "AB" or "CD"
• If found, it recursively calls the function with the substring obtained by removing the found substring from the start of the string, and updates the minimum length if the resulting string has a smaller length
• This process continues until no more occurrences of "AB" or "CD" can be found in the string.

Solution Code:

class Solution {
public:
    int minLength(string s) {
        int ans = s.size();
        for(int i = 0 ; i < s.size(); i++){
            if (s.substr(i, 2).compare("AB") == 0){
                ans = min(ans, minLength(s.substr(0, i) + s.substr(i+2)));
                break;
            } else if (s.substr(i, 2).compare("CD") == 0){
                ans = min(ans, minLength(s.substr(0, i) + s.substr(i+2)));
                break;
            }
        }
        return ans;
    }
};