题目难度:二星
考察点:字符串、模拟

方法:模拟

1.分析:

根据题意,我们可以对这n个字符串进行枚举,即判断字符串两两是否有重复的字符,如果没有就计算两个字符串的长度乘积,将n^2个字符串的长度乘积求出来,然后比较输出最大值即可。有几个小坑点:
(1). 处理输入问题,因为这个题的输入是比较恶心的,所以我们需要专门的处理一下输入,即输入的是一个字符串,然后将""之内的字符串全部提取出来,保存在一个vector数组中,具体可以详见代码。
(2). 判断s1,s2两个字符串是否有重复字符,那么我们可以首先定义一个标志数组ok[26] ,然后对s1进行遍历,ok[s1[i]-'a'] = true;, 然后在对s2进行遍历,如果在s2中找到有相同字符即ok[s2[i]-'a'] = true;的话直接return 0,否则继续往下进行遍历,直到s2的字符全部遍历完毕,发现没有相同字符,return s1和s2的字符串长度之积。
举个例子:
有两个字符串s1 = "abc", s2 = "dea"
在对s1遍历完毕之后,那么在ok数组中的表示就是ok[0] = ok[1] = ok[2] = true,其余的都是false,然后在对s2进行遍历:
当遍历到第一个字符d时,发现ok['d'-'a'=3] = false,那么继续往下遍历,
当遍历到第二个字符d时,发现ok['e'-'a'=4] = false,那么继续往下遍历,
当遍历到最后一个字符d时,发现ok['a'-'a'=0] = true,那么有相同字符,直接return 0。

算法实现:
(1). 输入字符串s
(2). 将字符串s进行处理,得到一个包含所有字符串的vector<string> a;
(3). 按照上述算法进行遍历,即i从1-n, j从1-n,得到两个字符串s[i]和s[j]的字符串长度之积,如果有相同字符,长度之积为0.,并比较最大值。
(4). 输出最大的字符串长度之积结果为ans。

2.复杂度分析:

时间复杂度:O(n^2)
空间复杂度:O(26)

3.代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
vector<string> get_vector(string s) {
    int i = 0, n = s.size();
    vector<string> ans;
    while(i < n) {
        if(i<n && s[i++]=='"') {
            string tmp = "";
            while(i<n && s[i]!='"') tmp += s[i++];
            ans.push_back(tmp);
            i++;
        }
    }
    return ans;
}
bool ok[26];
int get_ans(string s1, string s2) {
    memset(ok, false, sizeof ok);
    for(int i=0; i<s1.size(); i++) ok[s1[i]-'a'] = true;
    for(int i=0; i<s2.size(); i++) if(ok[s2[i]-'a']) return 0;
    return s1.size() * s2.size();
}
int main() {
    string s; cin>>s;
    vector<string> a = get_vector(s);
    int ans = 0;
    for(int i=0; i<a.size(); i++) {
        for(int j=0; j<a.size(); j++) {
            ans = max(ans, get_ans(a[i], a[j]));
        }
    }
    cout<<ans<<endl;
    return 0;
}