K 개의 고유 한 문자가있는 문자열의 하위 시퀀스 번호

Question

문제를 해결하고 싶고 코드가 작동하지 않아 도움이 필요합니다.

좋아, 그래서 시퀀스 S (입력 데이터)를 가지며 I는 별개의 문자 시퀀스 번호는 K (입력 데이터)와 동일해야한다는 시퀀스의 수를 찾아야

예 :

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

나는 조금 생각하고 있었고 인터넷에서 약간의 해답을 찾았지만 실제로 원하는 것을 찾지 못했습니다. 그래서 나는 모든 문자의 순서를 순서대로 찾아야한다고 생각하지만이 후에 무엇을해야할지 모르겠다. ...

Answer 1

가장 효율적인 해결책은 아니지만 여기에있다 : 반복을 통해 시작한다. 당신의 끈과, 모든 위치에 대해, 당신은 2 가지 일을 할 필요가 있습니다. 먼저, k 개의 다른 문자를 찾을 때까지 (그 주파수 배열을 사용) 또는 문자열의 끝에 도달 할 때까지 그 위치에서 반복합니다. 하위 시퀀스를 찾은 경우 + 1을 멈춘 위치에서 다시 반복하고 발견 한 문자가 이미 빈도 벡터에 있고 문자열의 끝에 도달하지 않은 경우 찾은 문자 수를 계산하십시오 . 그 번호에 1을 더하고 (첫 번째 서브 시퀀스 때문에) 거기에서 그 위치의 모든 서브 시퀀스를 찾는다. 그런 다음 첫 번째 색인을 증가시키고 계속하십시오.

Answer 2

루비 솔루션 :

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