Cannibal Characters - You want to minimize the length of the string s (Easy)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Try solving on Hacker Earth    Test Cases

Problem

You are given an integer n and a string s of size n composed of lower case english letters.

You can perform the following operation on it:

In one operation, you have to choose any character in the string s, then delete the first character to the left of the chosen character that is equal to the chosen character (if there exists) and delete the first character to the right of the chosen character that is equal to the chosen character (if there exists). 
Note that in one operation, the length of the string s is reduced by a maximum of two characters.
Task

You want to minimize the length of the string s.

Find the minimum number of operations that need to be performed to minimize the length of the string s.

Note:

Assume 1 based indexing.
Example

Assumptions :

n = 4
s = "abaa" (without quotes)
Approach:

Choose 3rd character in the string for 1st operation, this will delete the 1st character and 4th character in string s, the string becomes "ba".
The length of the string s can not be reduced further.
Hence, minimum number of operations needed to reduce the length of the string s to a minimum is 1.
Function Description

Complete the Minimum_Operations function provided in the editor. This function takes the following 2 parameters and returns the required answer:

n: Represents the length of string s.
s: Represents the string s.
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, which denotes the number of test cases. T also specifies the number of times you have to run the Minimum_Operations function on a different set of inputs.
For each test case:
First line contains an integer n.
Second line contains a string s.
Output format

For each test case in a new line, print the minimum number of operations required to minimize the length of string s.

Constraints




Brainstorming... Initial Thoughts

The problem is asking us to find the minimum number of operations required to minimize the length of a given string s. The operation involves choosing a character in the string and deleting the first occurrence of that character to the left and right of the chosen character.

To solve this problem, we can iterate through the string and count the occurrences of each character. We can then determine how many operations are needed to remove all occurrences of each character. The total number of operations will be the sum of the operations needed for each character.

If number of occurrences of a character is n: we need n // 2 operations to remove n-1 occurrences of that character.

Finally, we can sum up the operations needed for all characters to get the total minimum number of operations required to minimize the length of the string s.


Code Implementation


from collections import Counter

def Minimum_Operations (n, s):
    # Write your code here
    occ = Counter(s)
    chars = set(list(s))

    num_ops = 0
    for c in chars:
        if occ.get(c, 0) > 1:
            num_ops += occ.get(c, 0) // 2
    
    return num_ops


T = int(input())
for _ in range(T):
    n = int(input())
    s = input()

    out_ = Minimum_Operations(n, s)
    print (out_)