2021-12-27：给定一个字符串str，和一个正数k， str子序列的字符种数必须是k种，返回有多少子序列满足这个条件。 已知str中都是小写字母， 原始是取mod， 本节在尝试上，最难的， 搞出

2021-12-27：给定一个字符串str，和一个正数k，
str子序列的字符种数必须是k种，返回有多少子序列满足这个条件。
已知str中都是小写字母，
原始是取mod，
本节在尝试上，最难的，
搞出桶来，组合公式。
来自百度。

答案2021-12-27：

假设有3种字符，k=2，那么种类上就是3取2，然后2种字符词频，求2的n次方相乘，最后累加。
比如abbccc。
词频：a=1,b=2,c=3。
选a,b：1*(2^2-1)=3，
选b,c：(2^2-1)*(23-1)=21，
选a,c：1*(2^3-1)=7，
3+21+7=31。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {

    s := "abbccc"

    k := 2

    ret := nums(s, k)

    fmt.Println(ret)

}

func twoSelectOne(c bool, a, b int) int {

    if c {

        return a

    } else {

        return b

    }

}

func f(bu []int, index, rest int) int {

    if index == len(bu) {

        return twoSelectOne(rest == 0, 1, 0)

    }

    // 最后形成的子序列，一个index代表的字符也没有!

    p1 := f(bu, index+1, rest)

    // 最后形成的子序列，一定要包含index代表的字符，几个呢？(所有可能性都要算上！)

    p2 := 0

    if rest > 0 { // 剩余的种数，没耗尽，可以包含当前桶的字符

        p2 = (1<<bu[index] - 1) * f(bu, index+1, rest-1)

    }

    return p1 + p2

}

func nums(s string, k int) int {

    str := []byte(s)

    counts := make([]int, 26)

    for _, c := range str {

        counts[c-97]++

    }

    return ways(counts, 0, k)

}

func ways(c []int, i, r int) int {

    if r == 0 {

        return 1

    }

    if i == len(c) {

        return 0

    }

    // math(n) -> 2 ^ n -1

    return math(c[i])*ways(c, i+1, r-1) + ways(c, i+1, r)

}

// n个不同的球

// 挑出1个的方法数 + 挑出2个的方法数 + ... + 挑出n个的方法数为:

// C(n,1) + C(n,2) + ... + C(n,n) == (2 ^ n) -1

func math(n int) int {

    return (1 << n) - 1

}

执行结果如下：

左神java代码

2021-12-27：给定一个字符串str，和一个正数k， str子序列的字符种数必须是k种，返回有多少子序列满足这个条件。 已知str中都是小写字母， 原始是取mod， 本节在尝试上，最难的， 搞出的相关教程结束。