字符串长度最大乘积

[编程题]字符串长度最大乘积

热度指数：7091 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知一个字符串数组words，要求寻找其中两个没有重复字符的字符串，使得这两个字符串的长度乘积最大，输出这个最大的乘积。如：

words=["abcd","wxyh","defgh"], 其中不包含重复字符的两个字符串是"abcd"和"wxyh"，则输出16

words=["a","aa","aaa","aaaa"], 找不到满足要求的两个字符串，则输出0

数据范围：输入的字符串长度满足 $2 \le n \le 100 \$ ，保证只包含小写字母

输入描述:

Input:

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

输出描述:

Output:

4

示例1

输入

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

输出

备注:

Input中，不包含相同字符的有三对：
"ab"和"cd"
"a"和"cd"
"a"和"bcd"
所以字符串长度乘积的最大值是4

算法知识视频讲解

小谷围做题家

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)