12
\$\begingroup\$

I just wanted to get ideas on how to improve my algorithm, the requirements are as follows: You are given a string S consisting of letters 'a' and 'b'. You want to split it into three separate non-empty parts. The lengths of the parts can differ from one another.

In how many ways can you split S into three parts, such that each part contains the same number of letters 'a'?

Examples:

  1. Given S = "babaa", the function should return 2. The possible splits are: "ba | ba | a" and "bab | a | a".

  2. Given S = "ababa", the function should return 4. The possible splits are: "a | ba | ba", "a | bab | a", "ab | a | ba" and "ab | ab | a".

  3. Given S = "aba", the function should return 0. It is impossible to split S as required.

And my implementation is the following

function countA(str) {
  return (str.match(/a/g) || {}).length;
}

function solution(S) {
  let intervalCount = S.length - 1; 
  let waysToSplit = 0;
  for(let i = 1; i < intervalCount; i++) {
    for(let j = 1; j < intervalCount - i + 1; j++) {
      if(countA(S.slice(0, i)) === countA(S.slice(i, i + j)) &&
         countA(S.slice(i, i + j)) === countA(S.slice(i + j))) {
        waysToSplit += 1;
      }
    }
  }
  return waysToSplit;
}

console.log(solution('babaa')); // 2
console.log(solution('ababa')); // 4
console.log(solution('aba')); // 0
console.log(solution('bbbbb')); // 6
console.log(solution('aaabaaabaaa')); // 4

Final answer: I've assembled a final answer based on the two first answers which I think is the best one, thank you guys for your explanations :), I've added comments to explain what I've understood from each part.

const triangularNumber = n => (n * (n + 1)) / 2;

const solution = (S) => {
  debugger
  // clever and performant way to test if we can split in 3 parts
  const intervals = S.split('a');
  if (intervals.length % 3 !== 1) {
    return 0;
  }
 
  // Because we need the same number of a's in each split we need to divide the
  // number of a's by 3 so we know where the next split starts
  const splitPoint = (intervals.length - 1) / 3;
  //test if the string contains "a" or not, if the splitPoint is 0 it means the
  //string don't have any "a" in it, so we just calculate the triangular number 
  //sequence
  if(splitPoint === 0) {
    return triangularNumber(intervals[0].length - 2);
  } else {
    // the split point is the interval between the sequence of a, if this
    // interval is non-empty it means that we can split the string in diferent
    // ways, take for example the string 'aaabaaabaaa' the split interval is
    // 3 becase we need 3 a's in each split, the value of the 3 split is 'b'
    // which is length 1, the + 1 represents the before the value, because now 
    // we have two ways of spliting this stirng
    // aaa|baaa.... and aaab|bbb, 2 posibilities lets say we had 'bb' then 
    // we would have 'bb'.length + 1, because
    // aaa|bbaaa... aaab|baaa... and aaabb|aaa..., the final part is just 
    // doing the same thing for the second part of the split and multipliting 
    // both because they can happen simutaneously
    return (intervals[splitPoint].length + 1) * 
          (intervals[2 * splitPoint].length + 1)
  }
}
\$\endgroup\$
13
\$\begingroup\$

The most important insight that can be made here is that when there are as to split by, it's only the span of text between the end of the first match and the start of the last match that matter, and the rest is a simple counting problem based on the substring lengths. Look at a few examples.

Input:
babaa
  ba   // This is segment between the end of the first match
       // and start of the last match
// The string can be split like:
|ba|
// To find the number of split positions,
// identify how many times the left `|` can be moved
// without going over the middle `a`
// and do the same for the right `|`:
|ba|
b|a|

Input:
aaabaaabaaa
   baaab // Middle segment
|baaab|
// The left bar can vary between the left edge, and the next `a`:
|baaab
b|aaab
// The right bar can vary between the right edge, and the last `a`:
baaab|
baaa|b
// 2 possibilities for each bar, so total possibilities is 2*2=4

Input:
ababa
 bab // Middle segment
|bab // Left bar
b|ab // Left bar
bab| // Right bar
ba|b // Right bar
// 2*2=4 possibilities total

To figure out the number of possibilities for the left bar, just check the length of the substring between the start of the middle segment and the first a and add one. Do the same for the length of the substring between the final a in the middle segment and the end of the middle segment, then multiply them together.

That's for when when there are as in the input. If there aren't as in the input, it's completely different. Take a look at the pattern for the number of split possibilities for the following input lengths:

bb: impossible (must be split into non-empty parts)

b|b|b // 1 possibility

b|b|bb // 3 possibilities
b|bb|b
bb|b|b


b|b|bbb // 6 possibilities
b|bb|bb
b|bbb|b
bb|b|bb
bb|bb|b
bbb|b|b

b|b|bbbb // 10 possibilities
b|bb|bbb
b|bbb|bb
b|bbbb|b
bb|b|bbb
bb|bb|bb
bb|bbb|b
bbb|b|bb
bbb|bb|b
bbbb|b|b

b|b|bbbbb // 15 possibilities
b|bb|bbbb
b|bbb|bbb
b|bbbb|bb
b|bbbbb|b
bb|b|bbbb
bb|bb|bbb
bb|bbb|bb
bb|bbbb|b
bbb|b|bbb
bbb|bb|bb
bbb|bbb|b
bbbb|b|bb
bbbb|bb|b
bbbbb|b|b

0 1 3 6 10 15 See the pattern? These are triangular numbers. Given a string of length x, the number of possibilities is the x - 2th triangular number (zero-indexed per convention), which can be calculated by: T(n) = (n * (n + 1)) / 2. For example, given bbbbb, length 5, you want the 3rd (0-indexed) triangular number, which is calculated by (3 * 4) / 2 = 6.

Now let's put all this into code.

const triangularNumber = n => (n * (n + 1)) / 2;
const solution = (input) => {
  const aCount = (input.match(/a/g) || []).length;
  if (aCount % 3 !== 0) {
    // Cannot be split evenly among 3 parts:
    return 0;
  }
  if (aCount === 0) {
    return Math.max(triangularNumber(input.length - 2), 0);
  }
  // Remove the leading characters so that only the middle segment is left:
  let middleSection = input;
  for (let i = 0; i < aCount / 3; i++) {
    middleSection = middleSection.slice(middleSection.indexOf('a') + 1);
  }
  // Do the same for the trailing characters:
  for (let i = 0; i < aCount / 3; i++) {
    middleSection = middleSection.slice(0, middleSection.lastIndexOf('a'));
  }
  // Now identify the number of characters leading up to the first `a`
  // and the number of characters from the last `a` to the end:
  const leftSize = middleSection.indexOf('a');
  const rightSize = middleSection.length - middleSection.lastIndexOf('a') - 1;
  return (leftSize + 1) * (rightSize + 1);
};

console.log(solution('babaa')); // 2
console.log(solution('ababa')); // 4
console.log(solution('aba')); // 0
console.log(solution('bbbbb')); // 6
console.log(solution('aaabaaabaaa')); // 4

There are no nested loops, so this algorithm has an overall computational complexity of O(n).

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

Your algorithm is cubic against the length of the string, as it uses nested for loops that each run proportionally to the length of the string with a linear time countA function inside them. But it is possible to achieve a linear time algorithm.

Note first that you will always be putting the same letter a characters in each split regardless of the split points. It's only the b characters between them that move. So a simplified version of the problem is to figure out how to split the letter a characters evenly. And then figure out how many options this gives you with your b characters.

Step one, break into intervals.

const intervals = S.split('a');

This takes linear time proportional to the number of characters in the string.

Step two, reject if the number of intervals is not one more than divisible by three.

if (1 !== intervals.length % 3) {
    return 0;
}

Contrast this with your algorithm, where you will attempt to split aba into three strings in multiple ways even though it can't be split to meet the requirements.

This takes constant time, as length is just a property of the array.

Step three, return the number of potential combinations.

const split_point = (intervals.length - 1) / 3;
return (0 === split_point) ?  intervals[0].length
                           : (intervals[split_point].length + 1) * (intervals[2 * split_point].length + 1);

This works by finding the possible split points. These need to be between the first two groups of a characters and between the last two. Which we have as strings in the intervals array. The potential split points then are before the string and after each character in the string. This is equal to one more than the length of the string. Finally, we need to know how many combinations there are. So we multiply the number of split points in the first split by the number of split points in the second and that gives us the total number of combinations.

The case of no a characters in the string requires a special check to match your original algorithm. I'm not sure that this is correct. It could be a bug in your original approach. Consider the possibility that this should actually return 0 or 15 for the input "bbbbb".

For "bb", the splits are bb||, b|b|, b||b, |bb|, |b|b, ||bb. But you indicate that your algorithm (and this one) will return 3.

This takes constant time.

Overall, this algorithm is linear relative to the length of the string. Further, it will continue to be linear relative to the length of the string even if you increase the number of split points. It is \$\mathcal{O}(n + s)\$ where yours is \$\mathcal{O}(n^{s + 1})\$ with \$n\$ as the length of the string and \$s\$ as the number of split points.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer I'm trying to figure out your approach very interesting, bb will return 0 because you can't split bb into three non-empty parts \$\endgroup\$ – Marcell Monteiro Cruz Oct 30 at 16:09
4
\$\begingroup\$

Other answers have covered the algorithm so this answer will cover other aspects of review.

Good things

  • Strict equality comparisons are used
  • indentation is consistent
  • variables have limited scope

Bug with object length

Let’s look at that first function:

function countA(str) {
  return (str.match(/a/g) || {}).length;
}

String.prototype.match() returns “An Array whose contents depend on the presence or absence of the global (g) flag, or null if no matches are found.”1. So if no matches are found then it will return null, but this code will return an empty object in that case. And an object doesn’t have a length prosperity so the function would return undefined in that case.

console.log('object length: ', {}.length);
console.log('array length: ', [].length);

Suggestions

Declaring intervalCount

let intervalCount = S.length - 1; 

The value is never reassigned. It is recommended that all ES6 variables are declared using const by default. When you determine re-assignment is necessary, use let instead. This helps avoid bugs from accidental re-assignment.

Increment by one

This line:

waysToSplit += 1;

Can be simplified using the post-fix (Or pre-fix, since it is the only statement in the expression) increment operator:

waysToSplit++;

Whitespace

For better readability, popular JS style guides (e.g. Google, AirBnb) call for a single space before opening parenthesis. So lines like these:

for(let i = 1; i < intervalCount; i++) {
  for(let j = 1; j < intervalCount - i + 1; j++) {
    if(countA(S.slice(0, i)) === countA(S.slice(i, i + j)) &&)

are easier to read like this:

for (let i = 1; i < intervalCount; i++) {
  for (let j = 1; j < intervalCount - i + 1; j++) {
    if (countA(S.slice(0, i)) === countA(S.slice(i, i + j)) &&)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.