Change Character

help
,
#1

This question was asked in InterviewBit Academy Entrance Test on 16 Feb.

Given a string A of size N consisting of lowercase alphabets.
You can change at most B characters in the given string to any other lowercase alphabet such that the number of distinct characters in the string is minimized.
Find the minimum number of distinct characters in the resulting string.

Constraints :

1 \leq N \leq 10^{5}
0 \leq B \leq N

Input :
String A
Integer B

Output :
Integer denoting minimum number of distinct characters in the string.

Please help.

#2

change the characters with minimum appearence and make them equal to the gratest ones. The minimum ans will be 1 if the number of other characters in the string is equal to the B.

#3

calculate count of each character.Initialize flag as 0.Keep flag 1 for all characters starting from maximum count to minimum count(for count>=1) for b characters . then calculate no of characters(not count) whose flag is 0.

#4

Can you explain your approach with an example?

#5

I think this will work.

1 Like
#6

Yes, I believe it’ll work. Here’s @anurag_bhatt’s idea coded (in python):

n, b = map(int, input().split())
string = input()

char_count = {}

for char in string:
    if char not in char_count:
        char_count[char] = 0

    char_count[char] += 1

counts = sorted(char_count.values())

# Current number of distinct characters
answer = len(counts)

# Excluding the last element because there has to be atleast 1 character
for i in range(len(counts) - 1):
    # We can substitute all the characters
    # Assume you are substituting for the max occurred character
    if counts[i] <= b:
        b -= counts[i]
        answer -= 1

    # If we can't substitute all counts[i]
    # We definitely can't substitute for any upcoming values
    else:
        break

print(answer)
#7

Cool. Thanks.