## Friday, April 8, 2016

### Sherlock and Valid String - Hackerrank

https://www.hackerrank.com/challenges/sherlock-and-valid-string
A "valid" string is a string $S$ such that for all distinct characters in $S$ each such character occurs the same number of times in $S$.
For example, aabb is a valid string because the frequency of both characters a and b is $2$, whereasaabbc is not a valid string because the frequency of characters ab, and c is not the same.
Watson gives a string $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

  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");
}