[Hackerrank] – Sherlock and the Valid String Solution

1.9K

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.

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.

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: