All problems
No-Repeat N-gram Block Count
Problem
Count how many vocabulary tokens are blocked by a no-repeat n-gram constraint. A candidate token c is blocked when the n-gram formed by the last n - 1 tokens of tokens followed by c already occurs somewhere in tokens.
Return the number of blocked candidates in vocab, counting duplicates in vocab separately. Return 0 when n is less than 1 or there are fewer than n - 1 prefix tokens.
Hint
Build the set of seen n-grams, then test the last n - 1 tokens plus each candidate.
Test cases
case 1
in: [["a","b","c","a","b"],["a","b","c"],3]
expected: 1
case 2
in: [["a","b","c","a","b"],["a","b","c"],2]
expected: 1
case 3
in: [["a","a","b"],["a","b","c"],1]
expected: 2
case 4
in: [["a"],["a","b"],2]
expected: 0
case 5
in: [[],["a"],3]
expected: 0
Starter codePython
def no_repeat_ngram_block_count(tokens, vocab, n):
# Your code here
pass5 test cases · run your code against them in the editor