Split String

2.5

4 votes
Basics of Greedy Algorithms, Algorithms, Greedy Algorithms
Problem

You are given a string S. A string is called a split string if it follows both the conditions defined below:

  1. It can be divided into K contiguous substrings such that the first letter of these substrings is the same for all the substrings.
  2. It can be divided into K contiguous substrings such that the first letter of these substrings is distinct for all the substrings.

Print YES if S is a split string otherwise print NO.

Input Format:

  • The first line contains an integer T, denoting the number of test cases.
  • The first line of each test case contains two integers N and K.
  • The second line of each test case contains a string S, which consists of N lowercase English letters.

Output Format:

For each test case, print YES if S is a split string otherwise print NO.

Constraints:

1<=T<=10

1<=K<=N<=105

S consists of N lowercase English letters.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

First test case:-
It can be proven that the string S cannot follow the two conditions. Hence, the answer is NO

Second test case:-
It can be divided into ab, ac, and a, the first letter of the strings are the same.
It can be divided into a, ba, and ca, the first letter of the strings are distinct.
Hence, the answer is YES

Editor Image

?