Check if all characters of string contains same number of times

Question

I am working on below problem statement:

A string is valid if all characters of the string appear the same number of times. It is also valid if we 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 s, determine if it is valid. If so, return YES, otherwise return NO.

For example, if s=abc, it is a valid string because frequencies are {a:1,b:1,c:1} . So is s=abcc because we can remove one c and have 1 of each character in the remaining string. If s=abccc however, the string is not valid as we can only remove 1 occurrence of c. That would leave character frequencies of {a:1,b:1,c:2}.

I came up with below code but it's not working as expected and it is failing on this input abcdefghhgfedecba. It is printing "NO" but it should be "YES" for that input.

private static String isValid(String s) {
    if (s == null || s.equals("")) {
        return "NO";
    }
    Map<Character, Integer> frequencies = new HashMap<>();
    for (char ch : s.toLowerCase().toCharArray())
        frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1);

    int count = 0;
    // Iterating over values only
    for (Integer value : frequencies.values()) {
        if (value == 2) {
            count++;
        }
    }
    if (count >= 1) {
        return "YES";
    }
    return "NO";
}

What is wrong I am doing here? What is the best and efficient way to do this?

Answer 1

java 8

import java.util.*;
public class MyClass {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        System.out.println(isValid(scan.next()));

    }

    private static String isValid(String s) {
        if (s == null || s.equals("")) {
          return "NO";
        }

        // frequencies ( hashmap) character : frequency 
        // contains frequency of each character of given string input
        Map<Character, Integer> frequencies = new HashMap<>();
        for (char ch : s.toLowerCase().toCharArray())
          frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1);

........................................................................................................................................................

        // freqTypesCount ( hashmap) 
        // frequency_type : number_of_chars_having this frequency_type 
        Map<Integer, Integer> freqTypesCount = new HashMap<>();
        for (int ch : frequencies.values())
          freqTypesCount.put(ch, freqTypesCount.getOrDefault(ch, 0) + 1);


        if( freqTypesCount.size() == 1){
            // it means all the chars of string occurs same number of time
            return "YES";
        }
        else if( freqTypesCount.size() > 2){
            // aaabbbbccdd
            // a : 3 b: 4 c:2 d:2 --> {3:1, 4:1, 2:2}
            // we can't make this string a valid string just by deleting single char
            return "NO";
        }
        else{
            int valid_freq = Collections.max(freqTypesCount.entrySet(), Map.Entry.comparingByValue()).getKey(); 
            int deleted = 0;

            for (Map.Entry<Character, Integer> entry : frequencies.entrySet())
            { 
                int thisCharCount = entry.getValue();

                if(thisCharCount != valid_freq){

                    if(deleted == 0){
                        if(thisCharCount - 1 == valid_freq || thisCharCount - 1 == 0){
                            deleted += 1;
                        }
                        else{
                            return "NO";
                        }
                    }
                    else{
                         return "NO";
                    }
                }
            }

            return "YES" ;
        }
    }
}

.....................................................................................................................................................................

python 3

from collections import Counter

inp_string = input()

def isValidStr( string):
    char_counter_dict = Counter( string)
    count_type_counter_dict = Counter(char_counter_dict.values())

    if len(count_type_counter_dict) == 1:
        return "YES"
    elif len(count_type_counter_dict) > 2:
        return "NO"
    else:
        valid_freq = count_type_counter_dict.most_common()[0][0]

        deleted = 0

        for char,count in char_counter_dict.items():

            if count != valid_freq:

                if deleted == 0:
                    if count - 1 == valid_freq or count - 1 == 0:
                        deleted += 1

                    else:
                        return "NO"

                else:
                    return "NO"


        return "YES"

print(isValidStr(inp_string))

Answer 2

Below code works fine. What i am doing here is storing frequency of each character in an array and then convert it to list because we are gonna need that later point of time. next i converted list to set and removed zero from it because there will be zero present in list corresponding to character which are not present in input string. if set has only on element after removing zero means all element has same frequency hence return true. if set has more than two element means there is no way we can make it valid string by removing one character at one place hence return false. Now if set has two value, We take min and max value from set.we can make it valid if there are one character with one frequency that is what first if condition is for. Now second condition is for ,if difference b/w max and min is one and max has only one frequency then we can remove one char from max and make it valid.

static String isValid(String s) {

        Integer arr[] = new Integer[26];
        Arrays.fill(arr, 0);
        //fill the frequency of every character in array arr
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 97]++;
        }
        //convert array to list of integer     
        List<Integer> arrList = Arrays.asList(arr);

        //convert list to set and remove zero bcos zero correspond to char that is not present
        HashSet<Integer> set = new HashSet<Integer>(arrList);
        set.remove(new Integer(0));
        int len = set.size();
        // if size==1 means all freq are same
        if (len == 1)
            return "YES";
        else if (len == 2) {
            List<Integer> list = new ArrayList<>(set);
            int x = list.get(0);
            int y = list.get(1);
            int max = (x > y) ? x : y;
            int min = (x < y) ? x : y;

             // if min elemnnt has value one and freuency one
            if (Collections.frequency(arrList, min) == 1 && min == 1) {
                return "YES";
            }
          //if max-min==1 and there are only one elemnt with value=max      
         else if (max - min == 1) {
                if ((Collections.frequency(arrList, max) == 1)) {
                    return "YES";
                } else {
                    return "NO";
                }
            } 
          // if no of element is more than
          else {
                return "NO";
            }

        } else
            return "NO";
    }

Answer 3

Counting the frequencies is the right idea, although I'm not sure why you're checking if the values in the map are 2. Once I've counted these frequencies, I'd create a reversed map of the number of characters that have each frequency, and then:

1. If the map's size is 1, it means all the characters have the same frequency - the string is valid.
2. If the set's size is 2:
   • If the minimal frequency is 1 and there's only one character with that frequency the string is valid, since this character can simply be removed
   • If the minimal frequency is 1 less than the maximal frequency, and there's only one character with the maximal frequency the string is valid, since this character can be removed.
3. In any other case, the string will be invalid.

private static boolean isValid(String s) {
    TreeMap<Long, Long> frequencyCounts =
            s.chars()
             .boxed()
             // Frequency map
             .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
             .values()
             .stream()
             // Frequency of frequencies map
             .collect(Collectors.groupingBy
                                 (Function.identity(),
                                  TreeMap::new,
                                  Collectors.counting()));

    if (frequencyCounts.size() == 1) {
        return true;
    }

    if (frequencyCounts.size() == 2) {
        Iterator<Map.Entry<Long, Long>> iter = frequencyCounts.entrySet().iterator();
        Map.Entry<Long, Long> minEntry = iter.next();
        long minFrequency = minEntry.getKey();
        long numMinFrequency = minEntry.getValue();

        if (minFrequency == 1L && numMinFrequency == 1L) {
            return true;
        }

        Map.Entry<Long, Long> maxEntry = iter.next();
        long maxFrequency = maxEntry.getKey();
        long numMaxFrequency = maxEntry.getValue();
        if (numMaxFrequency == 1L && maxFrequency == minFrequency + 1L) {
            return true;
        }
    }

    return false;
}

EDIT:
To answer the question in the comments, the frequency map and "frequency of frequencies" map can also be constructed with Java 7's syntax, although it may not be as elegant:

Map<Character, Long> frequencies = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
    char c = s.charAt(i);
    if (frequencies.containsKey(c)) {
        frequencies.put(c, frequencies.get(c) + 1L);
    } else {
        frequencies.put(c, 1L);
    }
}

TreeMap<Long, Long> frequencyCounts = new TreeMap<>();
for (Long freq : frequencies.values()) {
    if (frequencyCounts.containsKey(freq)) {
        frequencyCounts.put(freq, frequencyCounts.get(freq) + 1L);
    } else {
        frequencyCounts.put(freq, 1L);
    }
}