Coding Interview Question and Answer: Longest Consecutive Characters

Key Takeaways

You're given a sequence of characters or string. And the problem here is writing a function that takes this string as the input and finds the longest subsequence within the string consisting of a single character. In this particular example, that's tripleB right here, which is longer than double A or double D, for example. And the return format of your function should be depending on your language either a hash table or a dictionary with a character as the key and the length as the value. And if you want to practice, pause the video right here and see if you can solve it and test your solution within 10 minutes. So how would I solve this problem? The key here is to go through this string only once from left to right so that we can solve this problem in big of n in time. And as we go through this string, there are only five variables that we are going to keep track of. Current for the current character that we're examining. Max count for the length of the longest sequence that we've seen so far consisting of a single character. Max car for the character that sequence is consisted of. Perf car for the previous character before the current character. And count for the length of the current sequence that we're examining. So let's say we're looking at the third character B. Current is B of course and max count is two because the longest sequence that we've seen so far consisting of a single character is double A right here and the length of that is two. Max car is a because that sequence is consisted of two A's. Pref is a because the previous character to the current character that we're looking at is A. count is one because that's the length of the current sequence of a single character that we're examining which happens to be here just a single character B. If instead we were looking at this B near the end count would be three because that's the length of the current sequence that we're examining and we'll be able to replace max count with three and max car with B. And when we reach the end of the string, we're going to use max count and max cure, which are three and b in this example to return a dictionary or hash table with B as a key and three as the corresponding value. Let's see what this solution might look like in code. We're going to write a function called longest which takes seek as the input and seek is of course the given sequence of characters. And just for convenience here, I'm going to assume that seek is always non-MPT. And the return value from this function will be a dictionary or hash table with the length of the longest sequence with a single character in this case three as the value and the corresponding key will be that character. First thing we need to do in this function is we need to initialize some variables max count, max card and pref card. It doesn't matter too much what we initialize them to. After that, we're going to run a for loop for each character, which we're going to call current in seek. In the for loop, we'll first check if the previous character is the same as the current character that we're looking at. For example, if current is the second d in the string, then it's the same as the previous character. So, in that case, we're going to increment count by one. If that's not the case, if the previous character is different from the current character that we're looking at, for example, if we're looking at the first D right here in the string, then we're going to reset count to be one. So when we're looking at the first D right here, we're essentially examining a sequence of a single character and the length of that is of course one. So count will also be one. But when we get to the second D, we're looking at a sequence of two D's and the length of that is two. So count will be two. If this new count is larger than max count, which is the largest count we've seen so far, then we're going to update max count to be count. And we're going to also update the corresponding character max car to be the current character. And after that, we're going to update per card to be the current character. And at the end of the function, of course, we're going to return a dictionary with max car as the key and max count as the value. That's my solution to this problem. And thanks for watching.