Sherlock and Valid String - Hackerrank

https://www.hackerrank.com/challenges/sherlock-and-valid-string

A "valid" string is a string S$S$ such that for all distinct characters in S$S$ each such character occurs the same number of times in S$S$.

For example, aabb is a valid string because the frequency of both characters a and b is 2$2$, whereasaabbc is not a valid string because the frequency of characters a, b, and c is not the same.

Watson gives a string S$S$ to Sherlock and asks him to remove some characters from the string such that the new string is a "valid" string.

Sherlock wants to know from you if it's possible to be done with less than or equal to one removal.

http://www.martinkysel.com/hackerrank-sherlock-and-valid-string-solution/

count the character counts for each character.

• if they are all equal – it means that all characters occur exactly N times and there is no removal needed
• if 2 or more have less or more characters – there is no way to fix the string in just 1 removal
• if exactly 1 char has a different count than all other characters – remove this char completely and S is fixed.

from collections import Counter

 

 

def isValid(S):

    char_map = Counter(S)

    char_occurence_map = Counter(char_map.values())

 

    if len(char_occurence_map) == 1:

        return True

 

    if len(char_occurence_map) == 2:

        for v in char_occurence_map.values():

            if v == 1:

                return True

 

    return False

https://gist.github.com/vamsigp/b5f1feb83247f24af835

https://www.hackerrank.com/rest/contests/101hack26/challenges/sherlock-and-valid-string/hackers/akshaypandian/download_solution
https://www.hackerrank.com/rest/contests/101hack26/challenges/sherlock-and-valid-string/hackers/starpointer/download_solution

  Scanner scan = new Scanner(System.in);
  String watson = scan.nextLine();
  Map<Character, Integer> countChar = new HashMap<Character, Integer>();
  Map<Integer, Integer> countCount = new HashMap<Integer, Integer>();
  int length = watson.length();
  int i;
  for (i = 0; i < length; i++) {
   char c = watson.charAt(i);
   if (countChar.containsKey(c)) {
    countChar.put(c, countChar.get(c) + 1);
   } else {
    countChar.put(c, 1);
   }
  }
  
  for(Map.Entry<Character, Integer> entry : countChar.entrySet()){
   if(countCount.containsKey(entry.getValue())){
    countCount.put(entry.getValue(), countCount.get(entry.getValue())+1);
   }
   else{
    countCount.put(entry.getValue(), 1);
   }
   
  }
  if(countCount.size() == 1){
   System.out.println("YES");
  }
  else if(countCount.size() == 2){
   if(countCount.containsValue(1)){
    System.out.println("YES");
   }
   else{
    System.out.println("NO");
   }
  }
  else{
   System.out.println("NO");
  }