Split String | Practice Problems

Split String

★★★★★

2.5

4 votes

Basics of Greedy Algorithms, Algorithms, Greedy Algorithms

Details

Submissions

Discussion

Editorial

Problem

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

It can be divided into $K$ contiguous substrings such that the first letter of these substrings is the same for all the substrings.
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 <= 10^5$

$S$ consists of $N$ lowercase English letters.

Sample Input

2
3 4 
xyz
5 3
abaca

Sample Output

NO
YES

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.

Contributers:

Rohit Pradhan

Geetartha Kaustav