Mfcttrf

I have worked out a solution for this problem, however I am trying to reach an O(1) solution without the use of two for loops. The output should read as a3b2c4d1 for the solution below.

i.e. I want to be able to describe which is a "greedy" approach and the tradeoffs of each.

Here is my current solution:

let countLetters = (str) => 
 let arr = str.split(''),
 map = ,
 ret = '';
 
 for (var i = 0; i < arr.length; i++) 
 map[arr[i]] = str.match(new RegExp(arr[i], 'g')).length
 
 
	for (let i in map) 
 	ret += `$i + map[i]`
 
 
 return ret;


console.log(countLetters('aaabbccccd'));

Can someone explain to me what is the time complexity of the current solution, and possible how to think in better terms of reaching a better time complexity?

Big $O$

Time complexity is a ratio of some input metric (e.g. the number of character in the string) to the number of instructions required to complete the function.

In this case the metric $n$ is the string length. The first loop that uses String.match must for each character check all characters to find a count. That means at least $n * n$ steps need to be performed to do the operation.

Thus the complexity of the function is said to be $O(n^2)$

If you think about how you would solve it on paper. You would go over each character once with a list of characters found adding 1 to each count as you find them. This would have a time complexity of $O(n)$

Maps use a hash function to locate an item $O(1)$. So the time complexity to find out if you have counted a character before is $O(1)$, rather than your regExp $O(n)$

function countLetters(str) 
 const charCounts = ;
 var result = "";
 for (const c of str) 
 if (charCounts[c]) charCounts[c] += 1 
 else charCounts[c] = 1 
 
 for (const [char, count] of Object.entries(charCounts)) 
 result += char + " has " + count + " ";
 
 return result;

The second loop to create the result, will count in the worst case each character again. Thus the number of instructions is $2n$ In big $O$ notation the scale $2$ is insignificant compared to powers, even if it was $1000000n$ we ignore the scale and make it just $n$

It can not be done with less complexity as you need to check every character at least once. Because you do not know what the characters are before you check them.

Style Notes.

• Use ; or not, never use them sometimes.


• Careful with indentation. You indent 4 and sometime 2 spaces, use either not both.


• Use Function declarations in favor of arrow functions when in global scope.


• Variables that do not change should be declared as constants const
  


• Use for of rather than for in