The problem description should include that you can remove every occurence of a character and the examples should support this. The current description is misleading.

Here is my solution in Java. It passed all test cases here. IMHO, this is not a straight forward problem.

static String isValid(String s) {
    final String GOOD = "YES";
    final String BAD = "NO";

    if(s.isEmpty()) return BAD;
    if(s.length() <= 3) return GOOD;

    int[] letters = new int[26];
    for(int i = 0; i < s.length(); i++){
        letters[s.charAt(i) - 'a']++;
    }
    Arrays.sort(letters);
    int i=0;
    while(letters[i]==0){
        i++;
    }
    //System.out.println(Arrays.toString(letters));
    int min = letters[i];   //the smallest frequency of some letter
    int max = letters[25]; // the largest frequency of some letter
    String ret = BAD;
    if(min == max) ret = GOOD;
    else{
        // remove one letter at higher frequency or the lower frequency 
        if(((max - min == 1) && (max > letters[24])) ||
            (min == 1) && (letters[i+1] == max))
            ret = GOOD;
    }
    return ret;
}

Good problem, but I'd probably mark it as easy or medium, not difficult.

I think this problem merits the medium rating it wound up at. It is very easy to say "this is easy" and throw an overly simple code at it that misses a test case or two. That both makes you appreciate that it probably is a medium problem and that test case writers are terribly underappreciated.

Any non-trivial work, you can't overestimate the importance of having great test cases that don't miss weird corner cases and funny things that will "hardly ever happen" == "all the time" when huge amounts of data come at you.

Even in my not-quite-big-data career I've seen the craziest things happen because with still huge amounts of real data coming in to your software the incredibly rare conicidences still happen and break your code which is rock-solid unless one of those bizarre corner cases hits it and brings it down. Hooray for sufficient test cases and those hard-working underappreciated heros who write them.

My code failed only on Test case 14. It turns out that this test case has a string of 100,000 character long. I'm using Java where the limit of string length is only 0xFFFF or 65535. Admin may want to look into this test.