Interview javascript foreach

Question

Q: Write a function called countLetters which accepts a string and returns the values as the number of times the letter appears in the string. Hi, Is there a more efficient way to solve that question?

O(n) solution, howto make it O(log n)

function countLetters(str){
    var splitArr = str.toLowerCase().split("");
    var obj = {};
    var letters = "abcdefghijklmnopqrstuvwxez";
  
    splitArr.forEach((letter)=>{
        if(letters.includes(letter)){
            if(letter in obj){
                obj[letter]++;
            } else{
                obj[letter] = 1;
               
            }
        }
    });
    return obj;
}
console.log(countLetters('Ellie'))

could also create an array of 26 elements and add accordingly - - you also have a typo where `y` should be btw... — Denis Tsoi, Dec 05 '17 at 03:04
Initialise `obj` to `{a:0, b:0, c:0, ...}` and then you don't need `.includes()`, you just need the `if(letter in obj) obj[letter]++` part without the `else`. — nnnnnn, Dec 05 '17 at 03:05
You can apply some optimizations, but you can't make it `O(log n)` since you still need to iterate over all elements to count occurrences. Correct me if I'm wrong. — pumbo, Dec 05 '17 at 03:05
You could use a regex to strip out all non alpha characters - `str.toLowerCase().replace(/[^a-z]/g, '').split('')` — fubar, Dec 05 '17 at 03:17
Did someone tell you it could be O(log n)? Is that actually the complete question, or were there more restrictions on the input (e.g. “it is almost sorted and contains O(log n) distinct characters”)? — Ry-, Dec 05 '17 at 03:17

fubar · Accepted Answer · 2017-12-05T03:20:34.287

0

This isn't O(log n) as that isn't achieveable given the problem at hand. I do however think this is a more succinct solution to the problem.

function countLetters(str){
  var letters = str.toLowerCase().replace(/[^a-z]/g, '').split('');
  
  return letters.reduce(function (counts, letter) {
    counts[letter] = (counts[letter] || 0) + 1;
    return counts;
  }, {});
}

console.log(countLetters('Hello World!'));

edited Dec 05 '17 at 03:20

answered Dec 05 '17 at 03:18

fubar

16,918
4
37
43

This isn’t O(log n). – Ry- Dec 05 '17 at 03:18
Agreed. But as has already been established from the comments on the question, O(log n) isn't possible. I was posting this more as an example as to how their solution could be improved. – fubar Dec 05 '17 at 03:19
1

@JaromandaX: `const countLetters = str => [...str.toLowerCase()].reduce((o, c) => (/[a-z]/.test(c) && (o[c] = ~~o[c] + 1), o), {});` – Ry- Dec 05 '17 at 03:29

Interview javascript foreach

1 Answers1