Minimum Deletions for Exact Pattern Count

Problem Statement

Minimum Deletions for Exact Pattern Count Problem Description You are given two lowercase strings A and B and an integer K . You may delete any letters you like from A (the letters that remain keep their original order). You want the remaining string to contain exactly K occurrences of B as a substring - a contiguous block of letters. Overlapping occurrences are counted separately : "aaa" contains the substring "aa" twice, at positions 0 and 1. Report the smallest number of letters you have to delete from A so that the remaining string contains exactly K occurrences of B . If no set of deletions can achieve exactly K occurrences, report -1 . Complete the function solve(K, A, B) , which returns that integer. Input The first line contains T , the number of test cases. Each test case is three lines: - a line with the integer K , the exact number of occurrences wanted; - a line with the string A ; - a line with the string B . Output For each test case print one line: the minimum number of