In this Sherlock and the Valid String HackerRank solution, Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just character at index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.
Example
This is a valid string because frequencies are .
This is a valid string because we can remove one and have of each character in the remaining string.
This string is not valid as we can only remove occurrence of . That leaves character frequencies of .
Function Description
Complete the isValid function in the editor below.
isValid has the following parameter(s):
- string s: a string
Returns
- string: either
YESorNO
Input Format
A single string .
Constraints
- Each character
Sample Input
aabbcd
Sample Output
NO
Explanation
is the minimum number of removals required to make it a valid string. It can be done in following two ways:
Remove c and d to get aabb.
Or remove a and b to get abcd.
Sherlock and the Valid String HackerRank solution
I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.
Problem Solution in C#
public static string isValid(string s)
{
var charFreq = s.Distinct()
.ToDictionary(c => c, c => s.Count(t => t == c));
var timesFreq = charFreq.Values.Distinct().
ToDictionary(f => f, f => charFreq.Count(cf => cf.Value == f))
.OrderBy(x => x.Value).ThenBy(x => x.Key).ToList();
return timesFreq.Count switch
{
1 => "YES",
2 => timesFreq[0] is { Key: 1, Value: 1 } || timesFreq[1].Key == timesFreq[0].Key - 1 ? "YES" : "NO",
_ => "NO"
};
}Problem Solution in JavaScript
function isValid(s) {
// Write your code here
let hastMap = {};
for(let i = 0; i<s.length;i++){
hastMap[s[i]] = (hastMap[s[i]] || 0) + 1;
}
const arr = Object.values(hastMap)
const check = arr.filter(e => e != arr[0]).length;
if(check > 1) {
return 'NO'
}else {
return 'YES'
}
}Problem Solution in Python
def isValid(s):
v = {}
for char in s:
if char in v.keys():
v[char] += 1
else:
v[char] = 1
a = list(v.values())
for i in range(len(set(a))):
if len(a) - a.count(a[i]) > 1:
return "NO"
return "YES"Problem Solution in Java
public static String isValid(String s) {
Map<Character, Integer> frequancy = new HashMap<>();
for(int i = 0; i < s.length(); i++){
frequancy.put(s.charAt(i), frequancy.getOrDefault(s.charAt(i), 0) + 1);
}
int n = frequancy.get(s.charAt(0));
boolean isRemoved = false;
for (Map.Entry<Character, Integer> e : frequancy.entrySet()) {
if(Math.abs(e.getValue() - n) == 1 ||
(Math.abs(e.getValue() - n) > 1 && e.getValue() == 1)){
if(!isRemoved){
isRemoved = true;
}else{
return "NO";
}
}else if(Math.abs(e.getValue() - n) > 1){
return "NO";
}
}
return "YES";
}Problem Solution in C++
string isValid(string s)
{
map<char,int> occurences;
for(int i = 0; i < s.size(); i++)
{
occurences[s[i]]++;
}
map<int, int> frequency;
for(const auto& el : occurences)
{
frequency[el.second]++;
}
if(frequency.size() < 2)
{
return "YES";
}
else if(frequency.size() > 2)
{
return "NO";
}
else if(frequency.size() == 2)
{
auto it = frequency.begin();
auto it2 = next(frequency.begin());
if(abs((*it).first - (*it2).first) == 1 &&
((*it).second == 1 || (*it2).second == 1))
{
return "YES";
}
if(abs((*it).first - (*it2).first) != 1)
{
if(((*it).second == 1 && (*it).first == 1) ||
((*it2).second == 1 && (*it2).first == 1))
{
return "YES";
}
}
}
return "NO";
}