首页 > 试题广场 >

字符串长度最大乘积

[编程题]字符串长度最大乘积
  • 热度指数:7023 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
已知一个字符串数组words,要求寻找其中两个没有重复字符的字符串,使得这两个字符串的长度乘积最大,输出这个最大的乘积。如:
words=["abcd","wxyh","defgh"], 其中不包含重复字符的两个字符串是"abcd"和"wxyh",则输出16
words=["a","aa","aaa","aaaa"], 找不到满足要求的两个字符串,则输出0

数据范围:输入的字符串长度满足 ,保证只包含小写字母

输入描述:
Input:

["a","ab","abc","cd","bcd","abcd"]


输出描述:
Output:

4
示例1

输入

["a","ab","abc","cd","bcd","abcd"]

输出

4

备注:
Input中,不包含相同字符的有三对:
"ab"和"cd"
"a"和"cd"
"a"和"bcd"
所以字符串长度乘积的最大值是4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution18_字符串长度最大乘积 {

    /**
     * 本来想着这种暴力方***超时,因为是在没想到好的方法....
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        str = str.substring(1,str.length()-1);//数据处理,去掉[ 和 ]括号
        str = str.replace("\"","");//去掉 ",注意用转移符\"
        String[] dic = str.split(",");
        int max_leng = 0;
        for (int i = 0; i < dic.length; i++) {
            for (int j = i+1; j < dic.length; j++) {
                if (noContain(dic[i], dic[j])) {
                    max_leng = Math.max(max_leng, dic[i].length() * dic[j].length());
                }
            }
        }
        System.out.println(max_leng);
    }

    //判断两个字符是否重复,只能每个字符每个字符的比较了
    private static boolean noContain(String s1, String s2) {
        for (int i = 0; i < s1.length(); i++) {
            if (s2.contains(s1.substring(i, i + 1))) {
                return false;
            }
        }
        return true;
    }
}
发表于 2019-08-05 17:07:50 回复(6)
import java.util.*;

/*
*将每个字符串映射为一个整数
*映射规则为:
*a-z分别对应整数二进制位的0-25位,若字符串包含某一个字符则对应位置为1
*然后两两比较整数,若两个整数的0-25位没有相同位都为1,说明这两个字符串符合条件,计算乘积
*/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String[] strs = input.substring(1, input.length() - 1).split(",");
        int maxVal = 0;
        
        //初始化一个int[] nums = int[26] 的数组,该数组存储的值为
        //nums[i] 存储 二进制位对应第i位为1的整数。
        int[] nums = new int[26];
        int all = 0;
        for (int i = 0; i < 26; ++i) {
            nums[i] = 1 << i;
            all += nums[i];
        }
        
        /**
        *遍历字符串  将每个字符串映射为一个整数存储在vals[i]中
        *映射规则如下
        *遍历该字符串中的每个字符,找到该字符对应的nums中的值与vals[i]相或
        */
        int[] vals = new int[strs.length];
        for (int i = 0; i < strs.length; ++i) {
            for (int j = 1; j < strs[i].length() - 1; ++j) {
                vals[i] |= nums[strs[i].charAt(j) - 'a'];
                if (j > 27 && vals[i] == all)//如果0-25位都为1则不需要计算后面的字符
                    break;
            }
            if (vals[i] != all) {
                for (int k = i - 1; k > 0; --k) {
                    //没有二进制位同时为1的位数时 此条件成立
                    if ((vals[k] ^ vals[i]) == (vals[k] + vals[i])) {
                        maxVal = Integer.max(maxVal, (strs[k].length() - 2) * (strs[i].length() - 2));
                    }
                }
            }
        }
        System.out.println(maxVal);
    }
}

发表于 2020-02-24 00:51:21 回复(1)
def max_product():
    a = raw_input().replace("[","").replace("]","").replace('"',"").split(",")
    b = []
    c = []
    if not a:
        return
    for i in range(len(a)):
        b.append(set(a[i])) #将输入的字符串转化成集合

    for i in range(len(b)-1):
        for j in range(i+1,len(b)):
            if b[i] & b[j] == set():
                c.append(len(b[i])*len(b[j])) #判断集合没有交集的相乘并存入数组
    if len(c) == 0:
        return 0
    return max(c)
print(max_product())
发表于 2019-08-27 20:02:26 回复(0)
暴力法对字符串进行两两配对,计算最长公共子序列长度,如果长度为0,说明两个字符串没有公共字符,更新一下最大乘积。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine().trim();
        line = line.replace("\"","");        // 去掉双引号
        String[] words = line.substring(1, line.length() - 1).split(",");
        int max = 0;
        for(int i = 0; i < words.length - 1; i++){
            for(int j = i + 1; j < words.length; j++) {
                // 不包含相同字符就更新一下乘积
                if(findLCS(words[i], words[i].length(), words[j], words[j].length()) == 0)
                    max = Math.max(max, words[i].length()*words[j].length());
            }
        }
        System.out.println(max);
    }
    
    // 求最长公共子序列的长度
    public static int findLCS(String A, int n, String B, int m) {
        // write code here
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(A.charAt(i - 1) == B.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
}


发表于 2021-02-19 15:35:30 回复(0)
bool pd(string s1,string s2)
{
    int len1=s1.size();
    int len2=s2.size();
    for(int i=0;i<len1;++i)
    {
        for(int j=0;j<len2;++j)
        {
            if(s1[i]==s2[j])
            {
                return false;
            }
        }
    }
    return true;
}
int main()
{
    string s;
    cin>>s;
    vector<string> temp;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='"')
        {
            string w="";
            i++;
            while(s[i]!='"')
            {
                w+=s[i];
                i++;
            }
            temp.push_back(w);
        }
    }
    
    int maxx=0;
    int len=temp.size();
   for(int i=0;i<len;++i)
   {
       for(int j=i+1;j<len;++j)
       {
           if(pd(temp[i],temp[j]))
              {
                  int res=(temp[i].size()*temp[j].size());
                  maxx=max(maxx,res);
              }
       }
   }
    cout<<maxx;
    return 0;
}
无脑暴力
发表于 2020-05-28 08:43:46 回复(0)
蛮力法+python set不包含重复元素特性
strs = input().replace("[","").replace("]","").replace('"',"").split(",")
maxLen = 0
for i in range(len(strs)-1):
    tempStrs = strs[i+1:len(strs)]
    for str2 in tempStrs:
        s1,s2 = set(strs[i]),set(str2)
        if len(s1)+len(s2)==len(s1|s2) and maxLen<len(s1)*len(s2):
                maxLen = len(s1)*len(s2)
print(maxLen)


发表于 2020-03-28 10:39:04 回复(0)
#include <bits/stdc++.h>
using namespace std;

int F(string s1, string s2){
    map<char,int> M;
    int n=s1.length(), m=s2.length();
    for(int i=0;i<n;i++){
        if(M.find(s1[i])==M.end())
            M[s1[i]]++;
        else
            return 0;
    }
    for(int i=0;i<m;i++){
        if(M.find(s2[i])==M.end())
            M[s2[i]]++;
        else
            return 0;
    }
    return n*m;
}

int main(){
    string s;
    getline(cin, s);
    vector<string> v;
    for(int i=0;i<s.length();i++){
        if(s[i]=='"'){
            string w = "";
            i++;
            while(s[i]!='"')
                w += s[i++];
            v.push_back(w);
        }
    }
    int r=0, n=v.size();
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            r = max(r, F(v[i], v[j]));
    cout<<r<<endl;

    return 0;
}

发表于 2020-01-03 11:47:14 回复(0)
#include <bits/stdc++.h>

using namespace std;

int mark[10002][26];

void read(vector<string> &vs){
  string s = "";
  bool flag = false;
  char c;
  while((c = getchar()) != ']'){
    if(c == '[' || c == ','){
      continue;
    }
    if(c == '"'){
      flag ^= 1;
      if(flag){
        continue;
      }
    }
    if(flag){
      s.push_back(c);
    } else {
      vs.push_back(s);
      s.clear();
    }
  }
}

int main(){
  vector<string> vs;
  int Max = 0;
  bool flag;
  read(vs);
  for (int i = 0; i < vs.size(); i++){
    for(char ch : vs[i]){
      mark[i][ch - 'a'] = 1;
    }
  }
  for (int i = 0; i < vs.size(); i++){
    for (int j = i + 1; j < vs.size(); j++){
      flag = true;
      for (char ch = 'a'; ch <= 'z'; ch++){
        if(mark[j][ch - 'a'] + mark[i][ch - 'a'] > 1){
          flag = false;
          break;
        }
      }
      if(flag){
        int mul = vs[i].length() * vs[j].length();
        Max = max(mul, Max);
      }
    }
  }
  cout << Max << "\n";
  return 0;
}

发表于 2019-09-09 12:18:46 回复(0)
直接暴力  这个输入对C++不太友好啊
#include<bits/stdc++.h>
using namespace std;

string s;
vector<string > ve;
bool taken[26];

void read(const string &s) {
    int i = 0, n = s.length();
    while(i < n) {
        if(i < n && s[i++] == '"')  {
            string tmp = "";
            while(i  <  n && s[i] != '"'){
                tmp.push_back(s[i++]);
            }
            ve.push_back(tmp);
			i++;
        }
    }
}

bool not_repeat(string s1, string s2) {
    memset(taken, 0, sizeof(taken));
    for(int i = 0; i < s1.length(); i++) taken[s1[i] -  'a'] = 1;
    for(int i = 0; i < s2.length(); i++) 
        if(taken[s2[i] - 'a']) return false;
    return true;
}

int main(){
    cin>>s; read(s);
    int max_res = 0, N = ve.size();
    for(int i = 0; i < N; i++)
        for(int j = i + 1; j < N; j++) 
            if(not_repeat(ve[i], ve[j])) 
                max_res = max(max_res, int(ve[i].length() * ve[j].length()));
    cout<<max_res<<endl;
}
/*
["a","ab","abc","cd","bcd","abcd"]
*/


发表于 2019-09-01 17:51:04 回复(0)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String sub = str.substring(1,str.length()-1);
        String[] strs  = sub.split(",");
        for (int i=0;i<strs.length;i++){
            if (strs[i].length() == 0)
                continue;
            strs[i] = strs[i].substring(1,strs[i].length()-1);
        }
        int max = 0;
        HashSet<Character> set = new HashSet<>();
        for (int i=0;i<strs.length;i++){
            for (int j=i+1;j<strs.length;j++){
                set.clear();
                int k;
                for (k=0;k<strs[i].length();k++){
                    set.add(strs[i].charAt(k));
                }
                for (k=0;k<strs[j].length();k++){
                    if (set.contains(strs[j].charAt(k)))
                        break;
                }
                if (k == strs[j].length()){
                    int length = strs[i].length()*strs[j].length();
                    if (length > max)
                        max = length;
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2019-08-03 20:21:44 回复(0)
"""
遍历所有情况判断
"""
import sys


def hava_same_char(a, b):
    for c in a:
        if c in b:
            return True
    return False


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    s = [c[1:-1] for c in input().strip()[1:-1].split(',')]
    ans = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if not hava_same_char(s[i], s[j]):
                ans = max(ans, len(s[i]) * len(s[j]))
    print(ans)

发表于 2019-07-10 12:44:11 回复(0)
/*
暴力求解。
不需要排序,最开始想错了。
注意:样例[]。
*/
import java.util.*;
class StringArray implements Comparable<StringArray> {
    String s;
    public StringArray(String s) {
        this.s = s;
    }
    public int compareTo(StringArray a) {
        return a.s.length() - this.s.length();
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        String strt = str.substring(1, str.length() - 1);
        String[] s = strt.split(",");
        int len = s.length;
        if (len <= 1) {
            System.out.println(0);
            return;
        }
        StringArray[] stringArrays = new StringArray[len];
        for (int i = 0; i < len; i++) {
            s[i] = s[i].substring(1, s[i].length() - 1);
            stringArrays[i] = new StringArray(s[i]);
        }
        Arrays.sort(stringArrays);
        int ans = 0;
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j < len; j++) {
                if (isNoSame(stringArrays[i].s, stringArrays[j].s)) {
                    int tmp = stringArrays[i].s.length() * stringArrays[j].s.length();
                    ans = Math.max(ans, tmp);
                }
            }
        System.out.println(ans);
    }

    static boolean isNoSame(String s1, String s2) {
        int[] cnt = new int[128];
        int len1 = s1.length();
        int len2 = s2.length();
        for (int i = 0; i < len1; i++) {
            cnt[s1.charAt(i)]++;
        }
        for (int i = 0; i < len2; i++) {
            if (cnt[s2.charAt(i)] > 0)
                return false;
        }
        return true;
    }
}

发表于 2019-06-29 14:29:38 回复(0)

暴力破解就完事啦

#include <bits/stdc++.h>
using namespace std;

int fun(string s1,string s2)
{
    set<char> s;
    for(auto it : s1)
    {
        if(s.count(it) == 0)
        {
            s.insert(it);
        }
        else
        {
            return 0;
        }
    }
    for(auto it : s2)
    {
        if(s.count(it) == 0)
        {
            s.insert(it);
        }
        else
        {
            return 0;
        }
    }
    int ans = s1.length()*s2.length();
    return ans;
}

int main()
{
    string str;
    getline(cin,str);
    vector<string> v;
    //分割字符串得到单词
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] == '"')
        {
            string word = "";
            i++;
            while(str[i] != '"')
            {
                word += str[i];
                i++;
            }
            //cout << word << endl;
            v.push_back(word);
        }
    }
    //暴力破解
    int ans = 0;   //输出结果
    for(int i = 0; i < v.size(); i++)
    {
        for(int j = i+1; j < v.size(); j++)
        {
            ans = max(ans,fun(v[i],v[j]));
        }
    }
    cout << ans << endl;
    return 0;
}
发表于 2019-07-08 20:59:59 回复(0)
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
    // Write your code here
    let line = await readline();
    let arr=line.replace(/[\[""\]]/g,'').split(',')  //去掉字符串的[]""
    // let arr=line.slice(1,-1).split(',').map(v=>v.slice(1,-1))
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i].split("").every((v) => !arr[j].includes(v))) {
                max = Math.max(max, arr[i].length * arr[j].length);
            }
        }
    }
    console.log(max);
})();

发表于 2024-01-06 00:40:59 回复(0)
package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    s,_:=in.ReadString('\n')
    s=s[1:len(s)-2]
    if len(s)==0{
        fmt.Print(0)
        return
    }
    arr:=strings.Split(s,",")
    for i,_:=range arr{
        arr[i]=arr[i][1:len(arr[i])-1]
        if len(arr[i])==0{
            fmt.Print(0)
            return
        }
    }
    ans:=0
    for i:=0;i<len(arr);i++{
        for j:=i+1;j<len(arr);j++{
            if comp(arr[i],arr[j]){
                if len(arr[i])*len(arr[j])>ans{
                    ans=len(arr[i])*len(arr[j])
                }
            }
        }
    }
    fmt.Print(ans)
}

func comp(s1,s2 string)bool{
    cnt:=map[byte]int{}
    for _,ch:=range []byte(s1+s2){
        cnt[ch]++
        if cnt[ch]>1{
            return false
        }
    }
    return true
}

发表于 2023-03-20 19:46:14 回复(0)
class Solution:
    def unrepeatedWords(self, word1:str, word2:str) -> int:
        for char in word1:
            if char in word2:
                return 0
        return len(word1) * len(word2)
    
if __name__ == '__main__':
    my_input = input()
    # 处理输入是关键!
    words = my_input[2:-2].split('","')
    
    maxValue = 0
    solution = Solution()
    for i in range(len(words)):
        for j in range(i + 1, len(words)):           
            ans = solution.unrepeatedWords(words[i], words[j])
            maxValue = max(ans, maxValue)
    print(maxValue)

发表于 2022-06-22 19:33:41 回复(0)
1、采用int存储字符串转化为bits,&操作O(1)实现比较
2、采用map优化过滤有相同bits,仅保留最大长度的一个
3、采用sort排序优化将较长的排在前面,最后两重循环,内层再次优化提前结束内层for循环。
3ms,376kb。
#include<bits/stdc++.h>
using namespace std;
struct cmp{
    bool operator()(const pair<int,int>&a,pair<int,int>&b)
    {
        return a.second>b.second;
    }
};

int main()
{
    vector<pair<int,int>> vec;
    map<int,int> mp; 
    char c;
    bool flag=false;
    getchar();//读取'['
    while(true)
    {
        int cur=0,len=0;
        int pre;
        flag=false;
        while((c=getchar())!='\"'&&c!=']');//读取到"
        if(c==']')break;
        while((c=getchar())!='\"'){
            cur^=1<<(c-'a');
            len++;
        }
        mp[cur]=max(mp[cur],len);
        c=getchar();
        if(c==']')
            break;
    }
    for(auto &i:mp)
    {
    	vec.push_back({i.first,i.second});
	}
	sort(vec.begin(),vec.end(),cmp());
    int res=0;    
    for(int i=0;i<vec.size();++i)
    {
        for(int j=i+1;j<vec.size()&&vec[i].second*vec[j].second>res;++j){
            //cout << vec[i].first << " " << vec[j].first << endl;
            if(!(vec[i].first&vec[j].first))
            {
                res=max(res,vec[i].second*vec[j].second);
            }
        }
    }
    cout << res << endl;
    return 0;
}


发表于 2021-01-31 21:56:49 回复(0)
w, a = input()[2: -2].split("\",\""), 0
for i in range(len(w) - 1):
    for j in range(i + 1, len(w)):
        if not set(w[i]) & set(w[j]): a = max(a, len(w[i]) * len(w[j]))
print(a)

发表于 2020-07-16 13:26:37 回复(0)
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int fun(string x, string y){
    /*
        用一个set容器把第一个字符串装进去,然后遍历第二个
        字符串,如果在set容器中找到和第二个字符串中的某个
        字符相同的元素,那就说明第二个字符串和第一个字符
        串存在重复。
    */
    set<char> st;
    for(auto u : x){
        st.insert(u); 
    }
    for(auto u : y){
        if(st.count(u) != 0)
            return 0;
    }
    return x.length()*y.length();
}
int main()
{ 
    vector<string> vec;
    string element;
    cin >> element;
    //字符串分割
    for(int i = 1; i < element.size() - 1; ++i){
        if(element[i] == '"'){
            //找到匹配的另一个”
            ++i;
            string temp = "";
            while(element[i] != '"'){
                temp += element[i];
                ++i;
            }
            vec.push_back(temp);
        }
    }

    //1. 没有重复  2.长度乘积最大
    int tempmax = 0;
    for(int i = 0; i < vec.size(); ++i){
        for(int j = i + 1; j < vec.size(); ++j){
            tempmax = max(tempmax, fun(vec[i], vec[j]));
        }
    }
    cout << tempmax << endl;
    return 0;
}

发表于 2020-06-01 22:25:50 回复(0)
#include <bits/stdc++.h>
using namespace std;
bool fun(string s1,string s2){
    int len1 = s1.size();
    int len2 = s2.size();
    for(int i=0; i<len1; i++){
        for(int j=0; j<len2; j++){
            if(s1[i]==s2[j]){
                return false;
                break;
            }
        }
    }
    return true;
}
int main(){
    string str;
    getline(cin,str);
    int size = str.size();
    vector<string> vec;
    for(int i=0; i<size; i++){
        if(str[i]=='"'){
            i++;
            string s="";
            while(str[i]!='"'){
                s += str[i];
                i++;
            }
            vec.push_back(s);
        }
    }
    int len = vec.size();
    int Max = 0;
    for(int i=0; i<len; i++){
        for(int j=0; j<len; j++){
            if(fun(vec[i],vec[j])){
                int res = vec[i].size()*vec[j].size();
                Max = max(res,Max);
            }
        }
    }
    cout << Max << endl;
    return 0;
}

发表于 2020-05-30 12:57:02 回复(0)