牛牛与ABC题解

牛牛有一个只包含A、B、C三个字符的字符串，牛牛想找到其中包含A、B、C这三个字符的最短子串的长度，只不过他不知道该如何解答，所以他想请你帮忙。
给定一个只包含A、B、C三个字符的字符串，返回其中包含A、B、C这三个字符的最短子串的长度，如果不存在该子串，请返回0。

题解：如果我们暴力去找必然会超时，不过我们考虑使用一种类似于dp的解法，先将abc三个字符所出现的位置都记录下来，然后记录这一轮中abc中出现的最大的索引和最小的索引的差值，然后使用一个变量ans去记录，不断地迭代ans = min(ans, max({a, b, c}) - min({a, b, c}) + 1)，就可以找到我们要的答案。
时间复杂度
空间复杂度
代码如下：

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    /**
     * 返回其中包含A、B、C这三个字符的最短子串的长度，如果不存在该子串，请返回0。​
     * @param s string字符串 代表题中所述字符串
     * @return int整型
     */
    int solve(string s)
    {
        int len = s.size();
        int ans = inf;
        int a, b, c;
        a = inf, b = inf, c = inf;
        for (int i = 0; i < len; i++)
        {
            if (s[i] == 'A')
                a = i;
            if (s[i] == 'B')
                b = i;
            if (s[i] == 'C')
                c = i;
            ans = min(ans, max({a, b, c}) - min({a, b, c}) + 1);
        }
        if (ans > 1000000)
        {
            return 0;
        }
        return ans;
    }
};