Sherlock and the Valid String HackerRank Problem

Sherlock and the Valid String | HackerRank

Task:- Given a string s, check whether string can be converted to a valid string or not by deleting at the most once character.

A string is said to be valid if all the characters in the string occur the same number of times.

Brute Force Approach:- The simplest way is to delete each element and check whether the remaining string is valid or not.

The time complexity of this approach would be O(N²) because we have to check the condition for N strings of length (N-1).

Efficient Approach:- First calculate frequency of each character in the string. Now put all the values(counts) of each character in a set.

• If the length of the set is 1, that means all the characters appear an equal number of times and the string is already valid.
• If the length of the set is greater than 2, we cannot convert that string to a valid string since we have to delete at least 2 elements to satisfy the condition.
• If the length of set is equal to 2, that means there are two different counts for characters and we may or may not be able to convert the string to a valid string:
• Let ‘a’ be the first value and ‘b’ be the second value. If any of the values is 1 and it is present just once in the frequency array, we can delete that element to make the string valid.

For eg: s=”aabbc”

Freq arr = [ 2, 2, 1, 0, 0, …. ]

In this case, we have two different counts i.e- a=2, b=1

a=2 tells there is at least one character which appears two times.

b=1 tells there is at least one character which appears one time.

• The same condition goes if the difference between these values is 1 and that value is present just once, we can delete that element to make the string valid.

For eg: s=”aabbccc”

Freq arr = [ 2, 2, 3, 0, 0, …. ]

In this case, we have two different counts i.e- a=2, b=3

b-a = 3–2 == 1 and count of b in freq arr==1, that means we can delete one instance of character ‘c’ to make the string valid.

Note that if only two values are present (a&b), one of them must be present only once, else we cannot convert the string to a valid string.

The time complexity of this approach would be O(N) since we only traverse the string once to calculate the frequency of each character. The rest of the operations are in constant(O(1)) time.

Code:-