Simple String

2

2 votes
String Algorithms, Algorithms, String, Basics of String Manipulation
Problem

You are given a String S. You can choose any two consecutive characters which are not equal and replace them with any other single character. You can repeat this process atmost K times.

Task

You have to determine the length of the smallest possible string which can be obtained.

Example

Assumption

  • N = 3
  • K = 2
  • S = abc

Approach

  • We can replace bc with b. Now, string S equals ab
  • We can replace ab with a. Now, string S equals a.

Therefore the length of the smallest possible string is 1.

Function description

Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the answer:

  • N: Represents an integer, the size of the string S
  • K: Represents an integer
  • S: Represents the string

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

  • The first line contains a single integer T that denotes the number of test cases. T also denotes the number of times you have to run the solve function on a different set of inputs.
  • For each test case:
    • The first line contains two space-separated integers N and K, denoting the length of string and the number of times we can perform replacement operation.
    • The second line contains a string denoting S.

Output format

For each test case, print in a new line the length of the smallest possible string which can be obtained.

Constraints
1T100
1N,K105
S contains only small letter English alphabets.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

 

Note - Use Fast Input/Output Methods for Big Test Cases.

Sample Input
1
4 1
aabc
Sample Output
3
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The first line contains the number of test cases, T = 1.

The first test case

Given

  • N = 4
  • K = 1
  • S = aabc

Approach

  • We can replace bc with d. Now, string S equals aad.

Therefore the length of the smallest possible string is 3.

Contributers:
Editor Image

?