LeetCode2696. Minimum String Length After Removing Substrings-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode2696. Minimum String Length After Removing Substrings。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings “AB” or “CD” from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new “AB” or “CD” substrings.

Example 1:

Input: s = “ABFCACDB”
Output: 2
Explanation: We can do the following operations:

Remove the substring “ABFCACDB”, so s = “FCACDB”.
Remove the substring “FCACDB”, so s = “FCAB”.
Remove the substring “FCAB”, so s = “FC”.
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.
Example 2:

Input: s = “ACBBD”
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Constraints:

1 <= s.length <= 100
s consists only of uppercase English letters.文章来源地址https://www.toymoban.com/news/detail-823726.html

二、题解

class Solution {
public:
    bool existed(string s){
        if(s.size() < 2) return false;
        int n = s.size();
        for(int i = 0;i < n - 1;i++){
            if(s[i] == 'A' && s[i + 1] == 'B') return true;
            if(s[i] == 'C' && s[i + 1] == 'D') return true;
        }
        return false;
    }
    int minLength(string s) {
        while(existed(s)){
            for(int i = 0;i < s.size() - 1;i++){
                if(s[i] == 'A' && s[i + 1] == 'B'){
                    s.erase(s.begin() + i);
                    s.erase(s.begin() + i);
                    i--;
                }
                else if(s[i] == 'C' && s[i + 1] == 'D'){
                    s.erase(s.begin() + i);
                    s.erase(s.begin() + i);
                    i--;
                }
                if(s.size() == 0) return 0;
            }
        }
        return s.size();
    }
};