Longest Consecutive Character

Account Required

This lesson is available if you sign in.
If you don't have an account, you can sign up for free.

Longest Consecutive Character

Sign in to access this content

You must sign in to access this content.
If you don't have an account you can sign up for free!

Problem

/**
* Given a string, returns the maximum consecutive repeating character in string.
* Examples:
* 'AAAABBBCCCCCCAAAA' => 'C'
* 'FooBarBaa' => 'o'
* '🌹👍👍🌹🌹👍👍🌹🌹🌹👍' => '🌹'
*/
export function longestConsecutiveCharacter(input: string): string {

}

Solution

/**
* Given a string, returns the maximum consecutive repeating character in string.
* Examples:
* 'AAAABBBCCCCCCAAAA' => 'C'
* 'FooBarBaa' => 'o'
* '🌹👍👍🌹🌹👍👍🌹🌹🌹👍' => '🌹'
*/
export function longestConsecutiveCharacter(input: string): string {
let longest = { char: '', count: 0 };
let current = { char: '', count: 0 };

for (const char of input) {
if (char === current.char) {
current.count++;
} else {
current = { char, count: 1 };
}

if (current.count > longest.count) {
longest = { ...current };
}
}

return longest.char;
}

Transcript

00:00 In our last lesson, we looked at the concept

00:02 of loop in variance

00:03 and how they can help you solve programming challenges.

00:06 In this lesson, we will build upon that by solving a problem

00:08 that is perhaps not as simple

00:10 as finding the minimum in N array

00:12 and solve it with the same concept

00:14 so you get a better understanding.

00:15 And this programming challenge actually comes

00:17 from a Google interview.

00:18 Celeste, jump in and have a look.

00:24 Here's the programming challenge statement.

00:26 Given a string return,

00:27 the maximum consecutive repeating character in the string.

00:31 Whenever you are given a programming challenge,

00:33 it's always a good idea to start off

00:34 by writing a few examples.

00:37 So in this first example,

00:38 the longest repeating character is character capital C

00:41 in the middle of the string.

00:43 In the second example, there are two repeating characters,

00:45 which are O and a,

00:47 but the first longest one that we experienced is O.

00:50 And we are going to assume that

00:51 that is what we want to return.

00:53 And just for amusement, here's an example

00:55 with emoji characters.

00:57 Now the next step of course,

00:58 to solve any programming challenge is

01:00 to write a skeleton function.

01:02 Our skeleton function is going to take an input string

01:05 and is going to return a string of length,

01:07 one containing the longest, consecutive repeating character.

01:10 Now, before we start looping

01:12 through the characters in the input string,

01:13 we maintain a few in variants.

01:15 The first one is a variable called longest,

01:17 which stores the longest character that we have experienced

01:20 so far, as well as

01:21 how many times this character repeated consecutively.

01:24 And of course, at the time when we haven't experienced any

01:27 of the characters from the input,

01:28 or by chance the input string is an empty one.

01:30 Returning an empty string is also an excellent choice.

01:34 Now as we progress through the various characters in the

01:36 input string, the current consecutive

01:38 character will change over time.

01:40 For the first example, initially it'll be A,

01:43 then it'll be B, then it'll be C,

01:45 and then it'll be a, again.

01:46 The solution to the problem is essentially maintaining this

01:49 current consecutive

01:50 and then constantly comparing it to the longest

01:52 that we have experienced previously.

01:55 And if at any point the current consecutive exceeds the

01:57 longest that we experienced previously,

01:59 we update the longest to the new value.

02:01 So in code, we start off by looping

02:03 through the input characters with a simple four off loop.

02:06 The next step is to maintain the current consecutive.

02:09 And we can do that by checking if the character is the same

02:12 as the current car.

02:14 And if it is, we've experienced one more

02:16 of the current character and we simply increment it count.

02:19 Otherwise, our current consecutive has changed

02:21 and we need to start off

02:22 with the new character at count one.

02:25 Now, in addition to maintaining the invariant about the

02:27 current consecutive character that we are experiencing,

02:30 we also maintain the invariant

02:31 that at any point within the loop longest points

02:34 to the longest current consecutive we have ever experienced.

02:38 And that is easily done

02:39 by simply checking the current count

02:41 against the longest count.

02:43 And if that is the case, we store the current into the

02:45 longest by creating a shallow copy using the

02:48 JavaScript spread operator.

02:50 And that's the entire solution to the problem.

02:52 By the time this fall loop terminates

02:54 because of maintaining the invariant about the longest

02:56 and the current, we can be guaranteed

02:58 that the longest is the maximum

02:59 that we have ever experienced.

03:01 Now, as a bonus, it's always good

03:03 to talk about space and time complexity.

03:05 So in terms of space complexity,

03:06 we are only maintaining two simple variables.

03:08 So it is constant OF one.

03:11 And in terms of space complexity, since we are looping

03:13 through all of the input characters,

03:14 it is directly dependent upon that and therefore OFN

03:18 or linear time.

03:19 And of course, as bonus points, if ever given time,

03:22 you should always add tests to verify

03:24 that your code functions as expected.

03:26 And as you can see for this particular case,

03:28 the tests are quite easy.

03:31 The key intuition for this particular lesson is

03:33 that we actually needed to maintain two kinds of variables.

03:36 One global maximum that we have experienced so far,

03:39 and one local chain that we are experiencing right now, so

03:42 that if it ever exceeds the global maximum,

03:44 we can update the global one.