具有K个不同字符的字符串的子序列数

-4

我想解决一个问题，我需要一些帮助，因为我的代码不起作用。具有K个不同字符的字符串的子序列数

好了，我有一个序列S（输入数据）以及我需要找到子序列的数目，使得不同的字符的序列号必须与K（输入数据）等于

实施例：

For S = abcaa and K = 3, the answer is 5. 
s1 = abc 
s2 = abca 
s3 = abcaa 
s4 = bca 
s5 = bcaa

我在想一点，我在网上看了一些答案，但我没有找到我真正想要的东西。所以，我认为，我必须找到在序列中的每个字符的频率，但我不知道在这之后该怎么办...

来源

2016-07-16 Vader

不是最有效的解决方案，但在这里你去：开始通过迭代你的字符串，并为每个位置，你需要做2件事情。首先，从该位置开始迭代，直到找到k个不同的字符（使用频率数组）或者直到您到达字符串的末尾。如果你找到了一个子序列，从停止+1的位置开始重新迭代，而当你发现的字符已经在你的频率向量中，而你还没有到达字符串的末尾时，计算你找到的字母数量。你给这个数字加1（因为第一个子序列），你去了，找到了那个位置的所有子序列。然后你增加你的第一个索引并继续。

来源

2016-07-16 20:43:55 Andrei

好，这会给你在以下情况下，错误答案：S = aaaabc – Vader

你确定吗？你不应该得到这个： aaaabc aaabc aabc aabc abc – Andrei

红宝石解决方案：

S="abcaa" 
k=3 
distinct_arr = [] 
result = 0 
S_arr = S.split("") 


while S_arr.length != 0 
    S_arr.each do |char| 
     if !distinct_arr.include? (char) 
      distinct_arr << char 
     end 
     if distinct_arr.length == k 
      result = result + 1 
     end 
     if distinct_arr.length == k + 1 
      break 
     end 
    end 
    S_arr.shift 
    distinct_arr = [] 
end 

puts result

来源

2016-07-16 21:59:29 Mihaiiii

具有K个不同字符的字符串的子序列数

回答

相关问题