HR_Sherlock and the Valid String.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NO\n",
      "YES\n",
      "NO\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem\n",
    "Sherlock considers a string, , to be valid if either of the following conditions are satisfied:\n",
    "All characters in have the same exact frequency (i.e., occur the same number of times). For example, is valid, but is not valid.\n",
    "Deleting exactly character from will result in all its characters having the same frequency. For example, and are valid because all their letters will have the same frequency if we remove occurrence of c, but is not valid because we'd need to remove characters.\n",
    "\n",
    "Given , can you determine if it's valid or not? If it's valid, print YES on a new line; otherwise, print NO instead.\n",
    "\n",
    "Input Format\n",
    "\n",
    "A single string denoting .\n",
    "\n",
    "Constraints\n",
    "\n",
    "    String consists of lowercase letters only (i.e., [a-z]).\n",
    "\n",
    "Output Format\n",
    "\n",
    "Print YES if string is valid; otherwise, print NO instead.\n",
    "\n",
    "Sample Input 0\n",
    "\n",
    "aabbcd\n",
    "\n",
    "Sample Output 0\n",
    "\n",
    "NO\n",
    "\n",
    "Explanation 0\n",
    "\n",
    "We would need to remove two characters from to make it valid, because a and b both have a frequency of and c and d both have a frequency of . This means is invalid because we'd need to remove more than character to make all its letters have the same frequency, so we print NO as our answer.\n",
    "\n",
    "Simple but tricky\n",
    "\n",
    "Logic:\n",
    "=====\n",
    "Go through the string once build a symbol count.\n",
    "Then use the frequncey of the symbol count.\n",
    "If there is only one frequncey.. then return true\n",
    "if greater than three retrun false\n",
    "if equal two , then the differnce between the frequencey is one return true.\n",
    "if the frequencey is itself one return true.\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "#!/bin/python3\n",
    "\n",
    "import sys\n",
    "import collections\n",
    "import operator\n",
    "\n",
    "def isValid(s):\n",
    "    d = collections.Counter()\n",
    "    for ch in s:\n",
    "        d[ch] += 1\n",
    "    #print (d)\n",
    "    freq = collections.Counter()\n",
    "    for key in d:\n",
    "        freq[d[key]] += 1\n",
    "    #print (freq)\n",
    "    if (len(freq)>2):\n",
    "        return \"NO\"\n",
    "    if (len(freq) == 1):\n",
    "        return \"YES\"\n",
    "    \n",
    "    first = True;\n",
    "    #print(freq)\n",
    "    u_big = 0\n",
    "    for u,v in sorted(freq.items(),key=operator.itemgetter(1),reverse=True):\n",
    "        if (first == True):\n",
    "            u_big = u\n",
    "            first = False\n",
    "            continue;\n",
    "        if v!= 1:\n",
    "            return \"NO\"\n",
    "    #print (u,v)\n",
    "    if (abs(u_big-u) == 1):\n",
    "        return \"YES\"\n",
    "    if (u==1):\n",
    "        return \"YES\"\n",
    "    # Complete this function\n",
    "    return \"NO\"\n",
    "\n",
    "print (isValid(\"aabccc\"))\n",
    "print (isValid(\"aabccb\"))\n",
    "print (isValid(\"asdfasdfasdfasdfasdfws\"))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}