Sherlock and the Valid String Solution

carlosbf
carlosbf
Sep 9, 2018 · 1 min read

This is one of the medium difficulty problems in the string manipulation section of hackerrank’s interview preparation kit problem set. Link here.

The problem states that given a string determine if all characters occur the same number of times. Additionally if there is a single character that occurs a different number of times you can ignore that character. aaa is a YES instance. aaabbc is a NO instance.

Solution

The problem domain only encompasses the ascii chars a-z so this is easy we just keep track of the occurences of the letters and then check if more than one character occurs a different number of times than the rest. The implementation is straight forward and just requires counting and then checking if the conditions apply to the resulting count.

Edit: The solution was update to handle the case abccc thanks to Jakob Svenningsson for noticing this.

Code

#include <bits/stdc++.h>using namespace std;string isValid(string s) {
const char * s_chars = s.c_str();
vector<int> occur(26);

for(int i = 0; i < s.length(); i++ ){
occur[s_chars[i] - 'a']++;
}

int max_occur =-1;
bool removed_char = false;
for(int i =0; i < 26; i++){
if(occur[i] == 0){
continue;
}else if(max_occur == -1){
max_occur = occur[i];
continue;
}else if(occur[i] == max_occur){
continue;
}else if(!removed_char && (occur[i] == max_occur + 1 || occur[i] == 1)){
removed_char = !removed_char;
continue;
}else{
return "NO";
}
}

return "YES";
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string s;
getline(cin, s);
string result = isValid(s);fout << result << "\n";fout.close();return 0;
}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade