Improving subLength function

So I managed to get a working version of the subLength() algorithm and it does what it needs to do. However, it takes up a fair few lines for a relatively simple task so I was wondering if there were any specific methods I could call or techniques I could implement to make this code more efficient and compact.

This is the link to the problem:
https://www.codecademy.com/paths/full-stack-engineer-career-path/tracks/fscp-javascript-syntax-part-ii/modules/fecp-practice-javascript-syntax-arrays-loops-objects-iterators/articles/fecp-javascript-practice-arrays-loops-objects-iterators

And here is my code:

const subLength = (word, letter) => { // Determine how many instances of letter there are in word let letterCount = 0; const chars = word.split(''); for (let i = 0; i < chars.length; i++) { if (chars[i] == letter) { letterCount++; }; }; // Return 0 if instances of letter is not 2, otherwise find distance between the 2 instances of letter if (letterCount == 2) { let index1 = 0; let index2 = 0; index1 = chars.indexOf(letter); index2 = chars.indexOf(letter, index1 + 1); return (index2 - index1) + 1; } else { return 0; }; }; console.log(subLength('javascript', 'a')); console.log(subLength('computer', 'z')); console.log(subLength('illicit', 'i'));

Any tips to improve my code would be greatly appreciated!

Hi,

The number of lines in a program is not correlated to the efficiency of the algorithm. Rather, the amount of work the algorithm has to do over large inputs is a better measure (not the only measure). This is calculated by checking the runtime cost of the operations and how often these operations run.

Another approach is by considering how different implementations perform. For example, recursive algorithms tend to perform worse that procedural algorithms when the big-O complexity is the same.

2 Likes

This uses the same methods as you do added by the filter method and saves many lines:

const subLength = (word, letter) => {
  if (word.split('').filter(w => w===letter).length !== 2) return 0
  return word.lastIndexOf(letter) - word.indexOf(letter) + 1
};

Not sure if the Big O notion is better.

1 Like

Big-O is N since constants are discarded. If we consider .split(), .filter(), .lastIndexOf(), .indexOf() all have to iterate over word then we have, `O(4N). None of the iterations are nested, else this would be a different picture.

Oddly enough, the first method (.split()) is sufficient enough to solve this problem.

const sublength = (word, letter) => {
  const y = word.split(letter)
  return y.length === 3 ? y[1].length + 2 : 0
}
// logs 18
console.log(sublength('hslkdsalfjflskjdfh', 'h'))
// logs 0
console.log(sublength('hslkdsahlfjflskjdfh', 'h'))
// logs 13
console.log(sublength('hkldsjflsdfhlsdkfjlsh', 'j'))
2 Likes

Aside

This question inspired the creation of a character string object to which we can afix proven methods and let it grow. Let it grow!

const chr$ = {
  sublength (word, chr) {
    const y = word.split(chr);
    return y.length === 3 ? y[1].length + 2 : 0;
  },
  substring (word, chr) {
    const y = word.split(chr);
    return y.length === 3 ? `${chr}${y[1]}${chr}` : ``;
  }
}
const {sublength, substring} = chr$
console.log(substring('hslkdsalfjflskjdfh', 'h'), 
            sublength('hslkdsalfjflskjdfh', 'h'))
console.log(substring('hslkdsahlfjflskjdfh', 'h'), 
            sublength('hslkdsahlfjflskjdfh', 'h'))
console.log(substring('hkldsjflsdfhlsdkfjlsh', 'j'), 
            sublength('hkldsjflsdfhlsdkfjlsh', 'j'))

CHR$

Thank you for the links. This prompted some further reading as the Wikipedia article was a bit of a struggle to wrap my head around initially but after reading the following article:

I can see why the efficiency of my algorithm would be O(n).

1 Like

It takes time but it’s really invaluable information if you plan to build anything that will scale! There’s a lot of youtube videos/lectures that cover the topic.

Thank you, this is a really neat solution! Chaining different methods together to reduce the number of lines used is something I’d like to work on to make my code more compact so I appreciate your solution.
I didn’t know lastIndexOf existed either so that’s useful to know about for the future. Cheers! :grin:

1 Like

You’re welcome. :slight_smile:
Have a look at @mtf 's solution, too. While my approach iterates through the array four times, his does only once. Less code and less calculations === much faster on a large scale…

Woah, this blew my mind :sweat_smile:
How come this algorithm works then? I don’t really understand the syntax of line 3 here

Ok now this is some high level stuff :sweat_smile:
I’ve not come across character string objects yet. What does

do?

I’ll interject here, as long as it’s O(n) it doesn’t matter what the coefficient is… O(4n)=O(n) in long-run behaviour (one can think of it being in the same family of functions).

The mathematical explanation is that if you take the limit as x->infinity of x/4x you will just get 1/4 (a constant), since the x’s divide out.

There would be an improvement in performance if it could be better than linear (something like log(n) or a constant operation). Which is not the case :slight_smile:

Then, as you take the limit as x->infinity of log(x)/4x or 100,000,000/4x you would get 0 (which signifies the denominator grows faster in the long-run).

If the the comparison was worse, say O(n^2), then lim x->inf x^2/4x is x/4, which will continue growing over time (indicating that it’s a less efficient function).

2 Likes

1 Like

Thanks for the clarification. I haven’t spent much time with Big O notation yet, just read about the concept. And it will probably take a bit of extra time until I get this explanation:

So far I thought that if you have – let’s say – an array of 1 million items it will take four times as long to run the function if you iterate over it 4x rather than just once.
Although I don’t run it 4 times completely, since the methods indexOf and lastIndexOf break after the item is found, right? Doesn’t that matter at all?

1 Like

Study how String.split() works. When we split on a character, and that character is not present, it returns the same string, only as a single element array, so it has length == 1.

> 'string'.split(' ')
[ 'string' ]
> 

When the character is present only once, then we get an array with two strings…

> 'string'.split('i')
[ 'str', 'ng' ]
> 

Let’s see what happens when there are exactly two of the characters…

> 'yesterday'.split('e')
[ 'y', 'st', 'rday' ]
> 

Since we split on the two characters that are there, they are not present so we have to put them back into the string, and as the array is only three elements long, then the middle element is the string of characters between those two. We’ve merely reconstructed the target string.

1 Like

It’s a matter of the theory,

So if we have an array of a million items:

1 for-loop of 1,000,000

is the same in the long-run as:

4 for-loops of 1,000,000

The key catch here is that it’s long-run. As numbers get astronomically high, a constant factor of 4 is not considered significant (or a constant factor of 1,000,000 for that matter). At least in theory.

The context is that it’s used as a relational algorithmic comparison. In practice (maybe higher-performance environments), constants have to be accounted for but so do implementations (like recursive vs. iterative and other issues) and systems/languages used. There’s a lot of good contextualization conversations here: algorithm - Why is the constant always dropped from big O analysis? - Stack Overflow

2 Likes