Minimum rotations

3.6

13 votes
Algorithms, String Manipulation, Two pointer
Problem

You are given a string s that contains lowercase alphabets. The length of this string is n. While performing an operation, you can rotate the string by one character in the clockwise direction.

The string must satisfy the following condition:

You are given a character c and two integers f and k. Determine the minimum number of operations that you must perform so that the prefix of length k has at least f occurrences of character c.

Note: It may be impossible to make the string satisfy this condition.

Input format

  • First line: t denoting the number of test cases
  • For each test case (2×t lines):
    • First line: Space-separated integers n, f, k, c 
    • Second line: A string of size n

Output format

For each test case, print a single line denoting the required minimum number of rotations if it is possible to satisfy the condition. Otherwise, print 1.

Constraints

1t101n1051fn1kncisalowercasealphabet

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, after 2 clockwise rotations we will get "ilnikh". The prefix of length 4 contains 2 occurences of 'i'.

In the second test case, it is impossible to achive 2 occurences of 'm' in prefiix of length 2 in "momo" after any number of rotations.

Editor Image

?