Working with equal occurrences of characters in a string of characters

Question

I have a little problem here. I am solving some random questions from my book. Here is the task:

Task

A balanced string is one in which every character in the string appears an equal number of times as every other character. For example, "ab", "aaabbb" and "ababaabb" are balanced, but "abb" and "abbbaa" are not.

Additionally, strings may also include a wildcard character, "*". This wildcard character can represent any other character you wish. Furthermore, wildcards must represent another character; they cannot be left unused. A wild balanced string is a string in which all wildcards can be transformed into characters in such a way to produce a simple balanced string.

This challenge involves writing a function balanced(s) to check whether s is balanced.

Input is restricted to strings containing upper and lowercase alphabetical characters and the "*" wildcard character. The input string will match the regular expression

^[A-Za-z*]$*

Other Examples:

balanced("a") ⟹ true

balanced("ab") ⟹ true

balanced("abc") ⟹ true

balanced("abcb") ⟹ false

balanced("Aaa") ⟹ false

balanced("***********") ⟹ true

I have been able to get some answers but my algorithm is really failing me. I am thinking if there is anything I can do to adjust this code:

function balanced(s) {
  const cMap = {};
  for (let c of s) {
    cMap[c] ? cMap[c]++ : (cMap[c] = 1);
  }
  const freq = new Set(Object.values(cMap));
  if(s.includes('*')){
    return true;
  }
  if (freq.size === 0 || freq.size === 1){
    return true;
  } 
  if (freq.size === 1) {
    const max = Math.max(...freq);
    const min = Math.min(...freq);
    }
  return false;
}

Answer 1

Proceeding mathematically

Another way to think about this is to simply do some arithmetic. To be balanced, each unique character after replacing the asterisks must occur the same number of times. So that number of times (counts) multiplied by the number of unique characters (letters) must equal the length of the input string (including the asterisks.) This count must be at least as large as the largest count of an individual character. And the number of letters in the output must be at least as large as the number of unique letters in the input. The only other restriction is that since the letters are taken from the lower- and upper-case letters, there can be no more than 52 of them.

In other words:

A string (of length `n`) is balanceable if 
  there exist positive integers `count` and `letters` 
    such that 
      `count` * `letters` = `n` and
      `letters` <= 52 and 
      `letters` >= number of unique letters in the input (ignoring asterisks) and 
      `count` >= max of the counts of each individual (non-asterisk) letter in the input

With a helper function to find all the factor-pairs for a number, we can then write this logic directly:

// double counts [x, x] for x^2 -- not an issue for this problem
const factorPairs = (n) =>
  [...Array (Math .floor (Math .sqrt (n)))] .map ((_, i) => i + 1)
    .flatMap (f => n % f == 0 ? [[f, n / f], [n / f, f]] : [])

const balanced = ([...ss]) => {
  const chars = [...new Set (ss .filter (s => s != '*'))]
  const counts = ss .reduce (
    (counts, s) => s == '*' ? counts : ((counts [s] += 1), counts),
    Object .fromEntries (chars .map (l => [l, 0]))
  )
  const maxCount = Math.max (... Object.values (counts))
  return factorPairs (ss .length) .some (
    ([count, letters]) =>
      letters <= 52 &&
      letters >= chars .length &&
      count >= maxCount
  )
}

const tests = [
  'a', 'ab', 'abc', 'abcb', 'Aaa', '***********',
  '****rfdd****', 'aaa**bbbb*', 'aaa**bbbb******',
  'C****F***R***US***R**D***YS*****H***', 'C****F***R***US***R**D***YS*****H**',
  'KSFVBX'
]

tests .forEach (s => console .log (`balanced("${s}") //=> ${balanced(s)}`))

.as-console-wrapper {max-height: 100% !important; top: 0}

factorPairs simply finds all the factoring of a number into ordered pairs of number. for instance, factorPairs (36) yields [[1, 36], [36, 1], [2, 18], [18, 2], [3, 12], [12, 3], [4, 9], [9, 4], [6, 6], [6, 6]]. Because we are only checking for the existence of one, we don't need to improve this function to return the values in a more logical order or to only return [6, 6] once (whenever the input is a perfect square.)

We test each result of the above (as [count, letters]) until we find one that matches and return true, or we make it through the list without finding one and return false.

Examples

So in testing this: 'C****F***R***US***R**D***YS*****H***', we have a string of length 36. We end up with these 8 unique characters: ['C', 'F', 'R', 'U', 'S', 'D', 'Y', 'H'], and these counts: {C: 1, F: 1, R: 2, U: 1, S: 2, D: 1, Y: 1, H: 1}, and our maxCount is 2

We then test the various factor-pairs generated for 36

• count: 1, letters: 36 (fails because count is less than 2)
• count: 36, letters: 1 (fails because letters is less than 8)
• count: 2, letters: 18 (succeeds, and we return true)

And we don't need to test the remaining factor-pairs.

An example of using 18 letters, twice each could be:

C****F***R***US***R**D***YS*****H***
CCaabFFbcRcdUUSdeeRffDDgYYSghhiiHHjj - balanced

Note that this is not necessarily the only pair that will work. For instance, if we'd made it to count: 4, letters: 9, we could also make it work:

C****F***R***US***R**D***YS*****H***
CCCCFFFFRRRUUUSUDDRDYDSYYYSSxxxxHHHH - balanced

But the question is whether there was any such solution, so we stop when finding the first one.

If, on the other hand, we had one fewer asterisk in the input, we would test this: 'C****F***R***US***R**D***YS*****H**', with a length of 35. We end up with the same 8 unique characters: ['C', 'F', 'R', 'U', 'S', 'D', 'Y', 'H'], and these same counts: {C: 1, F: 1, R: 2, U: 1, S: 2, D: 1, Y: 1, H: 1}, and our maxCount is still 2.

We then test the various factor-pairs generated for 35

• count: 1, letters: 35 (fails because count is less than 2)
• count: 35, letters: 1 (fails because letters is less than 8)
• count: 5, letters: 7 (fails because letters is less than 8)
• count: 7, letters: 5 (fails because letters is less than 8)

and we've run out of factor-pairs, so we return false.

An alternate formulation

There's nothing particularly interesting in the code itself. It does the obvious thing at each step. (Although do note the destructuring of the input string to balanced, turning the String into an array of characters.) But it does something I generally prefer not to do, using assignment statements and a return statement. I prefer to work with expressions instead of statements as much as possible. I also prefer to extract helper functions, even if they're only used once, if they help clarify the flow. So I'm might rewrite as shown here:

const range = (lo, hi) => 
  [... Array (hi - lo + 1)] .map ((_, i) =>  i + lo)

// double counts [x, x] for x^2 -- not an issue for this problem
const factorPairs = (n) =>
  range (1, Math .floor (Math .sqrt (n)))
    .flatMap (f => n % f == 0 ? [[f, n / f], [n / f, f]] : [])

const getUniqueChars = ([...ss]) => 
  [... new Set (ss .filter (s => s != '*'))] 

const maxOccurrences = ([...ss], chars) => 
  Math.max (... Object .values (ss .reduce (
    (counts, s) => s == '*' ? counts : ((counts [s] += 1), counts),
    Object .fromEntries (chars .map (l => [l, 0]))
  )))

const balanced = (
  str,
  chars = getUniqueChars (str),
  maxCount = maxOccurrences (str, chars)
) => factorPairs (str .length) .some (
  ([count, letters]) =>
    letters <= 52 &&
    letters >= chars .length &&
    count >= maxCount
)

const tests = [
  'a', 'ab', 'abc', 'abcb', 'Aaa', '***********',
  '****rfdd****', 'aaa**bbbb*', 'aaa**bbbb******',
  'C****F***R***US***R**D***YS*****H***', 'C****F***R***US***R**D***YS*****H**',
  'KSFVBX'
]

tests .forEach (s => console .log (`balanced("${s}") //=> ${balanced(s)}`))

.as-console-wrapper {max-height: 100% !important; top: 0}

But that changes nothing logically. The algorithm is the same.

Answer 2

Here is an algorithm that accomplishes this task:

First of all, sort the string:

var sorted = s.split("").sort().join("");

Now that the string is sorted, group all similar characters into an array. This is fairly easy to do using regular expressions:

var matches = sorted.match(/([A-Za-z])(\1)+/g);

If there are no matches (i.e. the string is empty or only has asterisks) then it is balanceable:

if (!matches) return true;

Next, get the number of asterisk * characters in the string:

var asterisks = sorted.match(/\*+/) ? sorted.match(/\*+/)[0].length : 0;

Now, find the most repeated character in the string and get the number of its occurences (i.e. find the mode of the string):

var maxocc = Math.max(...matches.map(match => match.length));

Calculate the number of required asterisks. This is done by subtracting the length of each of the matches from maxocc...

var reqAsterisks = matches.map(match => maxocc - match.length)

...then summing up the results:

.reduce((acc, val) => acc + val);

Get the number of extra asterisks by the subtracting the number of required asterisks from the total number of asterisks:

var remAsterisks = asterisks - reqAsterisks;

The question that arises now is, what to do with the remaining asterisks? You can either 1. distribute them evenly among the groups, 2. use them to create another group, or 3. do both at the same time. Note that you can do either or both of 1 and 2 multiple times. To do this, first define a variable that will hold the group length:

var groupLength = maxocc;

Then, repeatedly give each group one asterisk from the remaining asterisks. After that, check whether you can do 1 or 2 (described above) to get rid of the remaining asterisks. Everytime you do this, decrement remAsterisks by the number of asterisks you use and increment groupLength by one. This is accomplished by the following loop:

while(remAsterisks >= 0) {
  if(remAsterisks == 0 || !(remAsterisks % matches.length) || remAsterisks == groupLength) {
    return true;
  } else {
    remAsterisks -= matches.length;
    groupLength++;
  }
}

Here is the complete code

function balanced(s) {
  var sorted = s.split("").sort().join("");
  var matches = sorted.match(/([A-Za-z])(\1)*/g);
  if (!matches) return true;
  var asterisks = sorted.match(/\*+/) ? sorted.match(/\*+/)[0].length : 0;
  var maxocc = Math.max(...matches.map(match => match.length));
  var reqAsterisks = matches.map(match => maxocc - match.length).reduce((acc, val) => acc + val);
  var remAsterisks = asterisks - reqAsterisks;

  var groupLength = maxocc;
  while(remAsterisks >= 0) {
    if(remAsterisks == 0 || !(remAsterisks % matches.length) || remAsterisks == groupLength) {
      return true;
    } else {
      remAsterisks -= matches.length;
      groupLength++;
    }
  }
  return false;
}

console.log(balanced("a"));
console.log(balanced("ab"));
console.log(balanced("abc"));
console.log(balanced("abcb"));
console.log(balanced("Aaa"));
console.log(balanced("***********"));
console.log(balanced("aaa**bbbb******));