Skip to content

Instantly share code, notes, and snippets.

@FermiDirak
Created October 20, 2019 04:02
Show Gist options
  • Save FermiDirak/51cb34b353a28178367e9d2ec3f6c325 to your computer and use it in GitHub Desktop.
Save FermiDirak/51cb34b353a28178367e9d2ec3f6c325 to your computer and use it in GitHub Desktop.
var balancedString = function(s) {
const n4 = s.length / 4;
s = s.split('');
const balance = {
Q: 0,
W: 0,
E: 0,
R: 0,
}
s.forEach(c => {
balance[c] += 1;
});
let return_n = false;
Object.keys(balance).forEach(key => {
if (balance[key] === s.length) {
return_n = true;
}
balance[key] -= n4;
balance[key] *= -1;
});
if (isBalanced(balance)) {
return 0;
}
if (return_n) { return s.length * 3 / 4; }
let current = {
Q: balance.Q,
W: balance.W,
E: balance.E,
R: balance.R,
};
let start = 0;
let end = 0;
let min = Infinity;
while (end < s.length) {
current[s[end]] += 1;
end += 1;
if (isBalanced(current)) {
while (start < end) {
if (!isBalanced(current)) {
end = start;
current = {
Q: balance.Q,
W: balance.W,
E: balance.E,
R: balance.R,
};
break;
}
min = Math.min(min, end - start);
current[s[start]] -= 1;
start += 1;
}
}
}
return min;
};
function isBalanced(balance) {
return balance.Q >= 0 && balance.W >= 0 && balance.E >= 0 && balance.R >= 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment