improve run-length-encoding algorithm

Question

I've got string interview question regarding run-length-encoding and my solution is O(n). Is there any way to improve it:

input is AABBBCAAEE
output suppose to be A2B3C1A2E2

const firstString=(str)=>{
  const arr = str.split('');
  let counter = 1;
  let result ='';
  for (let i=0; i<arr.length; i++){
    if(arr[i] === arr[i+1]){
      counter++;
    } else {
      result +=arr[i]+counter;
      counter = 1;
    }
  } return result
};
firstString('AABBBCAAEE');

check this: [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Sphinx, Mar 07 '18 at 01:10
You have no choice but to look at each letter so I don't think you can do better than O(n). — Rocky Sims, Mar 07 '18 at 01:14
Are you asking for ways to improve the big O time? Or are you also interested in ways to improve it in general (like making the code prettier and more concise)? — Rocky Sims, Mar 07 '18 at 01:24
I was trying to see is there a way to improve in terms of Big O — BeckiD, Mar 08 '18 at 17:26

score 2 · Answer 1 · answered Mar 07 '18 at 01:29

One way that you can improve this is to not perform the split. Strings are also indexable:

let firstString = (str) => {
  if (str.length <= 0) {
    return "";
  }
  const result = [];
  result.push(str[0]);
  let counter = 1;
  for (let i = 1; i < str.length; i++) {
    if (result[result.length - 1] === str[i]) {
      counter++;
    } else {
      result.push(counter, str[i]);
      counter = 1;
    }
  }
  result.push(counter);
  return result.join("");
};

Ele · Accepted Answer · 2018-03-07T11:52:28.387

1

Using this approach with regex: Regex to match/group repeating characters in a string

Regex explanation: /((.)\2*)/g

var str = 'AABBBCAAEE';
var result = str.replace(/((.)\2*)/g, function(match) {
  var [letter] = match;
  return `${letter}${match.length}`;
});

console.log(result);

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

edited Mar 07 '18 at 11:52

answered Mar 07 '18 at 01:35

Ele

33,468
7
37
75

Would you happen to know the time complexity of this? Is it still O(n)? – David G Mar 07 '18 at 18:20
@0x499602D2 yes it's O(n) because depends of the String's length. This approach is fancier instead of an improvement in terms of complexity. – Ele Mar 07 '18 at 18:31
I was trying to see is there a way to improve in terms of Big O, but looks like it is impossible, and that solution looks more elegant – BeckiD Mar 08 '18 at 17:27

SaiBot · Answer 3 · 2018-03-07T13:29:51.047

1

What you want to achieve is run-length encoding.

There are quite a few of existing Javascript implementations for this problem.

edited Mar 07 '18 at 13:29

answered Mar 07 '18 at 12:02

SaiBot

3,595
1
13
19

score 0 · Answer 4 · answered Dec 07 '21 at 11:44

Python Implementation Time - O(n), Space - O(n)

def encode(_str):
    n = len(_str)

    if _str == _str[0] * n:
        return f'{n}{_str[0]}'

    i, _count = 1, 1
    encoding = ''

    while i < n:
        if _str[i] == _str[i-1]:
            _count += 1
        else:
            encoding += f'{_count}{_str[i-1]}'
            _count = 1

        i += 1

    encoding += f'{_count}{_str[i-1]}'  # last iteration

    return encoding


assert encode('WWWWWW') == '6W'
assert encode('WWWWWWWWWBBBBBBB') == '9W7B'
assert encode('WWWWWWWWWBBBBBBBR') == '9W7B1R'
assert encode('W') == '1W'

improve run-length-encoding algorithm

4 Answers4

Linked

Related