Mark As Completed Discussion

Good morning! Here's our prompt for today.

Let's define the "compacting" of a string as taking an input like the following: 'sstttrrrr'.

We want to take the number of sequential appearances (number of times it shows up in a row) of each letter:

SNIPPET
1s: 2
2t: 3
3r: 4

And denote them next to the original character in the string, getting rid of the duplicates. In our above example, our output is: 's2t3r4'.

How long is this compacted string? Could you write a method that takes in a string and returns the length of the compacted one? Could you solve it using only O(1) extra space?

Description

Here are few other examples:

SNIPPET
1compactLength('aabbbbbbbbbbbbb')
2// 5 because we end up with `a2b13`

Another to consider:

SNIPPET
1compactLength('s')
2// 1 because we still end up with just `s`

Constraints

  • Length of the given string <= 100000
  • The string comprises of ASCII characters
  • Expected time complexity : O(n)
  • Expected space complexity : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

PYTHON
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's our guided, illustrated walk-through.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.