Resolving HackerRank’s Sherlock and the Valid String

The challenge I tried to solve this week was Sherlock and the Valid String. This one was a special challenge for me since Hackerrank showed me that attempted to solve it 6 years ago, while practicing Javascript and never submitted a response that was worth all the points, so extra motivation. Here is the enunciate:

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

Example

s = abc

This is a valid string because frequencies are {a = 1, b = 1, c =1}.

s = abcc

This is a valid string because we can remove one c and have 1 of each character in the remaining string.

s = abccc

This string is not valid as we can only remove occurrence of c. That leaves character frequencies of {a = 1, b = 1, c =2}.

Sherlock and the Valid String | HackerRank

My Solution:

The trick to solve this one is to structure correctly the information about the repetition of the number of letters. Let’s assume we want to find out if s = abcc is a valid string. As the first step we need to get a mapping between the letter and the number of time they appear on the string, so for s we will get something like:

{a = 1, b = 1, c =2}

This step is ok because it allow us to get rid of unnecessary information like the order in which letters occur and focus only on their frequency. Anyway, we still need to go a step further and group the info in a way that let us know if deleting only 1 letter we could have a valid string. Something that could be done for this, is to produce another mapping from this first, but here getting as key, the difference frequencies in this first mapping and as a value the total number of letter that correspond to each frequency. For s we will have this:

{1 = 2 because 2 letter appear 1 time (a,b), 2 = 1 (c)}

This is where we wanted to get. From this we can infer very important info

• If this mapping has only 1 entry, it means that all letters share the same frequency of appearance, hence the string is valid
• If it has more than 2 entries, then it will have 3 difference frequencies of letters and it would be imposible that by removing one we could get a valid string
• If the number of entries is exactly 2, then it could be a valid string. There will be a frequency fmax that has most of letter assigned to it (key 1 in example from above) and another frequency fless with less letters assigned. For the string to be valid, fless frequency can have assigned only 1 letter, and the value of this frequency need to be 1 (so that when 1 is subtracted this letter disappear ) or equal to fmax + 1. In any other case it won’t be a valid string.

Code Solution:

public static String sherlockValidString(String cad) {
    HashMap<Character, Integer> charFrequencyMapping = new HashMap<>();

    for(int i = 0; i < cad.length(); i++) {
        char current = cad.charAt(i);

        charFrequencyMapping.merge(current, 1, (oldFreq, newFreq) -> oldFreq + newFreq);
    }

    HashMap<Integer, Integer> freqToAmountOfLetterMapping = new HashMap<>();

    for(Integer freq : charFrequencyMapping.values()) {
        freqToAmountOfLetterMapping.merge(freq, 1 ,(oldAmountOfLetter, newAmountOfLetter) -> oldAmountOfLetter + newAmountOfLetter);
    }

    if(freqToAmountOfLetterMapping.size() == 1) {
        return "YES";
    } else if (freqToAmountOfLetterMapping.size() == 2) {
        Integer[] frequencies = freqToAmountOfLetterMapping.keySet().toArray(new Integer[2]);

        int keyOfMoreFrequentLetter = freqToAmountOfLetterMapping.get(frequencies[0]) > freqToAmountOfLetterMapping.get(frequencies[1]) ? frequencies[0] : frequencies[1];
        int keyOfLessFrequentLetter = freqToAmountOfLetterMapping.get(frequencies[0]) > freqToAmountOfLetterMapping.get(frequencies[1]) ? frequencies[1] : frequencies[0];

        return freqToAmountOfLetterMapping.get(keyOfLessFrequentLetter) == 1 && (keyOfLessFrequentLetter - 1 == keyOfMoreFrequentLetter || keyOfLessFrequentLetter - 1 ==0) ?
                "YES" : "NO";
    } else {
        return "NO";
    }
}