求满足条件的最长子串的长度

题目描述

给定一个字符串，只包含字母和数字，按要求找出字符串中的最长(连续)子串的长度，字符串本身是其最长的子串，子串要求:

1、只包含 1 个字母(a~z,A~Z)，其余必须是数字:

2、字母可以在子串中的任意位置;

如果找不到满足要求的子串，如全是字母或全是数字，则返回-1。

http://oj.easycode.top/problem.php?id=1577

示例

输入：abC124ACb

输出：4

输入：a5

输出：2

输入：abb9

输出：2

思路

1. 方案一：前缀和 + 两层循环

   字符串中只有两种字符，一是“字母”，二是“数字”。题目要求只有一个字母，那么可以对照原字符串定义一个数组，字母为1，数组为0，再来一个数组维护前缀和，( sum[j] - sum[i] + a[i] ) 代表着区间 [i, j] 里字母的个数，如果为1，则这个子串是符合要求的，ans = max(ans, j - i + 1);

2. 方案二：前缀和 + 滑动窗口

   定义一个left下标、一个right下标，来维护符合条件的子串区间。

   感觉求符合某条件的最长子串问题都能这么解决。

Code1

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    //freopen("00input.txt", "r", stdin);
    string s;
    while (cin >> s){
        int sz = s.size();
        vector<int> vec;
        for(int i = 0; i < sz; ++i) {
            if(s[i] >= '0' && s[i] <= '9') {
                vec.push_back(0);
            } else {
                vec.push_back(1);
            }
        }
        vector<int> sum;
        sum.push_back(vec[0]);
        for(int i = 1; i < sz; ++i) {
            sum.push_back(sum[i - 1] + vec[i]);
        }
        int ans = -1;
        for(int i = 0; i < sz; ++i) {
            for(int j = i + 1; j < sz; ++j) {
                if(sum[j] - sum[i] + vec[i] == 1) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Code2

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    //freopen("00input.txt", "r", stdin);
    string s;
    while (cin >> s){
        int sz = s.size();
        vector<int> vec;
        for(int i = 0; i < sz; ++i) {
            if(s[i] >= '0' && s[i] <= '9') {
                vec.push_back(0);
            } else {
                vec.push_back(1);
            }
        }
        vector<int> sum;
        sum.push_back(vec[0]);
        for(int i = 1; i < sz; ++i) {
            sum.push_back(sum[i - 1] + vec[i]);
        }
        int ans = -1, left = 0, right = 0;
        while (left <= right && left < sz && right < sz) {
            int num = sum[right] - sum[left] + vec[left];
            if(num == 1) {
                ans = max(ans, right - left + 1);
                right++;
            } else if(num < 1){
                right++;
            } else if(num > 1) {
                left++;
            }
        }
        cout << (ans == 1 ? -1 : ans) << '\n';
    }
    return 0;
}