字符串转换为整数（str子序列的字符）

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)*(2^3-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代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class39/Code03_SequenceKDifferentKinds.java)