Hello everyone, today, while going through the problem of Sherlock & Valid String, I literally tried a lot and was not getting a simple and sober solution.
In fact, when I myself started implementing it, I found that the problem is not that complicated the way the solutions are available in other blogs, so I started the problem and here is the solution I came up with.
Explanation
Suppose the input was aabbc:
In fact, when I myself started implementing it, I found that the problem is not that complicated the way the solutions are available in other blogs, so I started the problem and here is the solution I came up with.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | function isValid(s) { const countMap = {}; const countList = []; const arr = s.split(''); arr.forEach((a) => countMap[a] = (countMap[a] || 0) + 1); Object.keys(countMap).forEach(k => countList.push(countMap[k])); countList.sort(); const countSet = new Set(countList); const len = countList.length; if (countSet.size > 2) { return 'NO'; } else if (countSet.size === 1) { return 'YES'; } else if (countSet.size === 2) { const firstNum = countList[0]; const lastNum = countList[len - 1]; const lastList = countList.slice(1); const firstList = countList.slice(0, len - 1); const lastListSet = new Set(lastList); const firstListSet = new Set(firstList); return ( (lastListSet.size === 1 && firstNum === 1) || (lastListSet.size === 1 && lastNum - firstNum === 1) || (firstListSet.size === 1 && lastNum - firstNum === 1) ) ? 'YES' : 'NO'; } } |
Explanation
Suppose the input was aabbc:
- Create a countMap with the number of occurrences of each character.
- countMap = { a: 2, b: 2, c:1 };
- Make a list of the values of above maps( not keys ) and sort it.
- countList = [1, 2, 2]
- Convert countList to countSet
- countSet = [1, 2]
- If (countSet.size > 2) the solution is not possible.
- If (countSet.size === 1), we have the "YES"
- If (countSet.size === 2), we have to process:
- We will create 6 variables for our ease, those are:
- firstNum i.e first number of countList (sorted) = 1 (for our example)
- lastList i.e sub array of countList from 1..end = [2, 2]
- lastListSet i.e set over lastList, for removing duplicates = [2]
- lastNum i.e last number of countList (sorted) = 2
- firstList i.e sub array of countList from 0..end-1 = [1, 2]
- firstListSet i.e set over firstList, for removing duplicates = [1, 2]
- There are only 3 conditions which is "YES" those are:
- [ 1, X, X, X, X]
- [ X-1, X-1, X-1, X-1, X]
- [X, X, X, X, X+1]
- For our example 2.1 is true
- Apart from them there is no other way, a String will give "YES" and thats what we did
Happy coding,
:)
No comments:
Post a Comment