In real world horses **neigh**, and you can count them by listening to them.\n\nFor this problem you will be given an input string consisting of lowercases letters which represents combination of **neigh** of different horses.\n\nYou need to return an integer corresponding to minimum number of distinct horses which can produce the given sequence.\n\nIf the input string is not a combination of **valid neigh** from different horses return -1.\n\n**Example 1:**\n```\nInput: "nei"\nOutput: -1\nExplanation: Not a valid neigh.\n```\n\n**Example 2:**\n```\nInput: "neighneigh"\nOutput: 1\nExplanation: Single horse yelling neigh two times.\n```\n\n**Example 3:**\n```\nInput: "neingeighh"\nOutput: 2\nExplanation: Second horse can be seen speaking before the first one finished.\n```\n\n**Example 4:**\n```\nInput: "inghgeihhnnehegiggniienehgiinininnggeiiggheiinennihinihnigiiiheiehnigniehhnhhihheegenigiiienghihgnheneneiineeiihgegnnehgennheihhhgieehghigininniggineenignihnenhenehheggeghhgeeghegnihnghiiennegnhiengnegeneihegnenhinihhineiehhnhnihihinhnhgginhnninigieggginhhhiinheiiihegiegeenngggnhieneeenigiinnhiggneneegiiheihggghnhiinhiheiniegiiehnhggehengehigegnggnegenghhggehgeneehnhhngnheiggiggneieegnhegnhegnniieenhheighennheeghneeegehhhiihhegiehggiehgihhngneneheeiieeengieenninnhihheeeeeehehghenihggheeihgiigigiiggneheinhegghninheeihhiheeiehininngigiiiegiignghgehineehhnnginggiginehhhheenehhhegegehhniheeehegignnghhieeiiihhnhieginneneigihhnihiieiiigheinnginhnihnnehiieeeghieegngnnnhiieiheghnnineegnheegnhehighngeenhingegneghhinhienheenhihiehnnnghnghegeiingeiigeghieeigeheniegiignhhnighginiehghngninngeinnngingheingghginegeegghnneennnenieginhnihhieihgnghigiggnnhniheiigienhiiggienehgegihgignhhneehegh"\nOutput: -1\n```\n\nI saw this question in an interview and my inclination was to find the substrings that were "neigh" and then find subsequences that have the same characters as neigh but were not contiguous. I wasn\'t able to solve it in time. Has anyone seen a similar prolem? I want to use it as practice to figure out if there is an underlying concept/trick to learn. Thanks!

In real world horses neigh, and you can count them by listening to them.\n\nFor this problem you will be given an input string consisting of lowercases letters 