Home Strings [Hackerrank] – Sherlock and the Valid String Solution

[Hackerrank] – Sherlock and the Valid String Solution

by nikoo28
6 comments

Question: Given a string, Sherlock considers it valid if all the characters in the string occur the same number of time. However, a string is also valid if the frequencies are same after removing any one character.

Example 1:
Input: str = “aabbcd”
Output: NO

Example 2:
Input: str = “abcc”
Output: YES

Problem Statement:

Let us try to simplify the problem statement first.

Sherlock needs to verify if a given string is valid. A string is valid under 2 conditions:

  1. All characters of the string appear the same number of times.
  2. If you can delete any one character from the string to achieve condition #1.

For example if I have the string “abc”

character | frequency --------------------- a | 1 --------------------- b | 1 --------------------- c | 1

All characters have the same frequency, and hence the string is valid. However, if the given string is “abcc”.

character | frequency --------------------- a | 1 --------------------- b | 1 --------------------- c | 2

Sherlock can make this into a valid string by deleting the character c. Then each character will again have the frequency 1.

some extra sample test cases for sherlock valid string
Fig: Some more sample test cases

Brute Force Method:

A Brute Force way to solve this problem would be:

  1. Create a map and find out the frequency of each character.
  2. If all the frequencies are same, it is a valid string.
  3. If not, start from the first character in the array and delete the first character.
  4. Repeat steps 1 and 2.
  5. Do this for all the characters. If the string is valid, we will find our result in the loop.

This approach will work perfectly and Sherlock will be able to successfully identify the valid string. But, if your string size is very large, then you will end up creating a lot of frequency maps. Moreover, you will need additional computation time just to verify if all the frequencies are same.

brute force method to identify valid string
Fig: Brute Force method to verify all possible character deletions

Efficient Solution:

This is one of the classic problems where you need to focus on the conditions of truth. You need to just analyze under what conditions the string would be valid. One important thing to note is that we are free to delete any character from the string. Hence, it would be a good idea to just look at the frequencies and ignore the characters.

Example: For string “ABCDEEDCBAE“, you have the frequency map as:

character | frequency --------------------- a | 2 --------------------- b | 2 --------------------- c | 2 --------------------- d | 2 --------------------- e | 3

In this case you can just play around with the frequencies and create a frequency array.

freq[] = {2, 2, 2, 2, 3}

Upon thinking about the problem, there are only 3 conditions under which Sherlock can make a valid string.

  1. If all frequencies are same
  2. If all frequencies are same and only one of them is 1. (That means we can delete that character occurring only once)
  3. If all the frequencies are same and only of the frequencies is higher than the rest by 1. (That means we can delete that extra character)

Code:

public String isValid(String s) { Map<Character, Integer> charFreqMap = new HashMap<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int freq = charFreqMap.getOrDefault(c, 0); charFreqMap.put(c, ++freq); } int[] arr = new int[charFreqMap.size()]; int idx = 0; for (Map.Entry<Character, Integer> characterIntegerEntry : charFreqMap.entrySet()) { arr[idx++] = characterIntegerEntry.getValue(); } Arrays.sort(arr); if (charFreqMap.size() == 1) return "YES"; int first = arr[0]; int second = arr[1]; int secondLast = arr[arr.length - 2]; int last = arr[arr.length - 1]; // If first and last are same, then all frequencies are same if (first == last) return "YES"; // If first is 1, and all other characters have 1 frequency if (first == 1 && second == last) return "YES"; // If all are same and last character has just 1 extra count if (first == second && second == secondLast && secondLast == (last - 1)) return "YES"; // Else invalid string return "NO"; }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

Video Explanation:

You may also like

6 comments

Rahul Agrahari September 14, 2021 - 12:41

bro u r applying sort and time complexity is o(n) how is it possible

Reply
nikoo28 September 20, 2021 - 10:52

Hi Rahul, when you have to sort a limited set of numbers, you can implement sorting techniques that work in O(n) time.
In this particular question, we have alphabets, and they range from 1-26.

So, your range is fixed. In those scenarios, if you apply Counting Sort or Radix Sort, you can achieve an O(n) time complexity.

Reply
Mr. hustle June 9, 2021 - 03:09

why didn’t you directly compare first and second last??…what is the use of middleman second??.

Reply
nikoo28 June 9, 2021 - 09:34

yea, I realized it later. We can just compare first and last.

Reply
hago January 5, 2021 - 17:15

Hi buddy,
Thanks for the excellent explanation. But I don’t understand why are you checking for (second == secondLast). When you explain your code I don’t think you have mentioned anything about it.

Please clarify.

Regards

Reply
nikoo28 January 5, 2021 - 21:36

Hi,

I believe you are talking about the third case. (If all are same and last character has just 1 extra count)

We need to return “YES”, if all characters are same, except the last integer.
Suppose you have some sorted integers,
We compare the first and second number. They are same.
And then if the second number is same as the second last number, it would mean that all the numbers in between are same.

Hence, completing our condition.

Let me know if you are still facing trouble understanding this. I would recommend you write down a few test cases yourself. You will be able to see what I am talking about. :)

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More