2124-检查是否所有 A 都在 B 之前

给你一个仅由字符 'a' 和 'b' 组成的字符串 s 。如果字符串中每个 __'a' 都出现在每个
__'b' __ 之前，返回 true ；否则，返回 false 。

示例 1：

**输入：** s = "aaabbb"
**输出：** true
**解释：**
'a' 位于下标 0、1 和 2 ；而 'b' 位于下标 3、4 和 5 。
因此，每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

示例 2：

**输入：** s = "abab"
**输出：** false
**解释：**
存在一个 'a' 位于下标 2 ，而一个 'b' 位于下标 1 。
因此，不能满足每个 'a' 都出现在每个 'b' 之前，所以返回 false 。

示例 3：

**输入：** s = "bbb"
**输出：** true
**解释：**
不存在 'a' ，因此可以视作每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

提示：

1 <= s.length <= 100
s[i] 为 'a' 或 'b'

方法一：比较下标

思路与算法

我们可以考虑题目中命题的等价命题。

在字符串中含有 a' 和 b’ 的情况下「字符串中每个 a' 都在 b’ 之前」等价于「字符串中 a' **最后一次**出现的下标在 b’ 第一次出现的下标之前」。那么对于这种情况，我们可以顺序遍历字符串 s，找到 a' **最后一次**出现的下标 last}_a 与 b’ 第一次出现的下标 first}_b，并比较这两个下标。如果 last}_a < \textit{first}_b，则说明字符串中每个 a' 都在 b’ 之前，此时我们返回 true 作为答案；反之则不是，我们返回 false。

除此之外，字符串 s 还有可能出现不存在 a' 或 b’ 的情况。假设 s 的长度为 n，此时我们只需要将 last}_a 的初值设置为小于所有合法下标的 -1，并将 first}_b 的初始下标设置为大于所有合法下标的 n，即可保证这两种情况均被视为满足条件，且返回 true。

代码

[sol1-C++]class Solution {
public:
    bool checkString(string s) {
        int n = s.size();
        int lasta = -1;   // 'a' 最后一次出现的下标
        int firstb = n;   // 'b' 第一次出现的下标
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'a') {
                lasta = max(lasta, i);
            }
            else {
                firstb = min(firstb, i);
            }
        }
        return lasta < firstb;
    }
};

[sol1-Python3]class Solution:
    def checkString(self, s: str) -> bool:
        n = len(s)
        lasta = -1   # 'a' 最后一次出现的下标
        firstb = n   # 'b' 第一次出现的下标
        for i in range(n):
            if s[i] == 'a':
                lasta = max(lasta, i)
            else:
                firstb = min(firstb, i)
        return lasta < firstb

复杂度分析

时间复杂度：O(n)，其中 n 为 s 的长度。即为遍历维护下标的时间复杂度。
空间复杂度：O(1)。

方法二：寻找子串

思路与算法

我们也可以考虑题目中条件的否命题，即「字符串中存在 b' 在 a’ 之前」。由于字符串仅由 a' 和 b’ 构成，因此这等价于「字符串中存在子字符串 “ba”」。

那么我们只需要判断字符串 s 中是否存在子串 “ba”，如果存在，则说明并不是每个 a' 都在 b’ 之前，我们返回 false 作为答案；反之则返回 true。

代码

[sol1-C++]class Solution {
public:
    bool checkString(string s) {
        return s.find("ba") == string::npos;
    }
};

[sol1-Python3]class Solution:
    def checkString(self, s: str) -> bool:
        return s.find("ba") == -1

复杂度分析

时间复杂度：O(n)，其中 n 为 s 的长度。即为遍历寻找长度为 2 子串的时间复杂度。
空间复杂度：O(1)。