Skip to content

Instantly share code, notes, and snippets.

@m-esm
Created January 23, 2021 19:07
Show Gist options
  • Save m-esm/0a650c0f11a9ede0091f402d7ca53677 to your computer and use it in GitHub Desktop.
Save m-esm/0a650c0f11a9ede0091f402d7ca53677 to your computer and use it in GitHub Desktop.
const _ = require('lodash');
/**
Write a function checking that the given string is valid. We consider a string to be valid if all the characters of the string have exactly the same frequency.
Examples:
"aabbcc" is a valid string
"aabbccc" is an invalid string
*/
function stringIsValid(input: string) : boolean {
const map = {};
for( let i = 0; i < input.length; i++){
// O(1)
map[input[i]] = (map[input[i]] || 0) + 1;
}
const set = new Set(Object.values(map));
const keysSet = new Set(Object.keys(map));
if(set.size !== keysSet.size)
return false;
if(set.size === 1)
return true;
if(set.size > 2)
return false;
let smallerOne;
let biggerOne;
if(set[0] > set[1]){
biggerOne = 0;
smallerOne = 1;
}else{
biggerOne = 1;
smallerOne = 0;
}
const setValues = Array.from(set) as number[];
if(setValues[biggerOne] - 1 !== setValues[smallerOne])
return false;
return true;
}
const samples = [
{ text: "aabbcc", expect: true},
{ text: "aabbba", expect: true},
{ text: "aabbccc", expect: true},
{ text: "aabbcccddd", expect: false},
]
for(let sample of samples){
if(stringIsValid(sample.text) !== sample.expect){
throw new Error("invalid string: " + sample.text);
}
}
console.log('Finished');
// time complexity: O(n)
// space complexity: O(n)
// aabbcc
// aabbba
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment