LeetCode解法汇总2696. 删除子串后的字符串最小长度
目录链接：
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目：
https://github.com/September26/java-algorithms
原题链接：. - 力扣（LeetCode）
描述：
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。
通过执行操作，删除所有 "AB" 和 "CD" 子串，返回可获得的最终字符串的 最小 可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。
示例 1：
输入：s = "ABFCACDB" 输出：2 解释：你可以执行下述操作： - 从 "ABFCACDB" 中删除子串 "AB"，得到 s = "FCACDB" 。 - 从 "FCACDB" 中删除子串 "CD"，得到 s = "FCAB" 。 - 从 "FCAB" 中删除子串 "AB"，得到 s = "FC" 。 最终字符串的长度为 2 。 可以证明 2 是可获得的最小长度。
示例 2：
输入：s = "ACBBD" 输出：5 解释：无法执行操作，字符串长度不变。
提示：
1 <= s.length <= 100s仅由大写英文字母组成
解题思路：
这题还是比较简单的，因为s的长度为100以内，所以可以直接按照题目的描述去实现。时间复杂度其实是O(n2)。
如果这题的长度改为10W，则肯定就不行了，那时候就需要把时间复杂度限制到O(n)了。这时，就需要从前向后寻找AB或者CD，删除后，检查删除位置的前后是否构成新的AB或者CD，如果是则继续删除，而不是每次都从头查询。
代码：
class Solution {
public:int minLength(string s){while (true){bool flag = true;size_t index = s.find("AB");if (index != std::string::npos){s = s.substr(0, index) + s.substr(index + 2, s.size() - index - 2);flag &= false;}index = s.find("CD");if (index != std::string::npos){s = s.substr(0, index) + s.substr(index + 2, s.size() - index - 2);flag &= false;}if (flag){break;}}return s.size();}
};