Coding Interview Question and Answer: Longest Consecutive Characters

Given a string, find the longest subsequence consisting of a single character. Example: longest("ABAACDDDBBA") should return {'D': 3}.

(You'll get a 30-day trial with the link)

[Kyanzes]

Actually, you can slightly optimize:

if len(MyString) - lengthOfMyString < maxCount
return currentResults
endif

since there is no way to have a longer sequence of letters in the rest of the string. The more massive the string/task the more it is worth it to do this check.

[superman]

def LCC(string):
old_char = string[0]
count = 1
temp = old_char
maximum = 1
for i in range(len(string)-1):
char = string[i+1]
if char == old_char:
count += 1
if count > maximum:
maximum = count
temp = char
else:
count = 1
old_char = char
return temp, maximum

print(LCC("AABCDDBBBEA"))


I've done this in like 2 minutes I'm a CS student so I guess this is not optimal but I'm pretty happy it works :D
(obivously I didn't watch the video before coding it)

[chuckywang]

You don't need to compare count > max_count every time in the loop. You just need to do it when prev_char !== current, since that's what "ends" a count.

[RealMcDudu]

You don't really have to hold the previous char and the current char. You could do it a bit differently, starting on the 2nd character and continuing counting until you reach a different char, then updating the counters. Also, if you can, it's better to return a simple tuple and not a hash table, as you're not really using the hashtables functionalities... C# syntax follows:

static Tuple<char, int> s)
{
if(String.IsNullOrEmpty(s))
return null;
char maxChar = s[0];
int maxCount = 1;
int currentCount = 1;
for (int i = 1; i < s.Length; i++)
{
if (s[i] == s[i - 1])
currentCount++;
else
{
if(currentCount > maxCount)
{
maxChar = s[i - 1];
maxCount = currentCount;
currentCount = 1;
}
}
}
return new Tuple<char, int> (maxChar, maxCount);
}

[ashishkulkarnii]

Here's the Python code, if anyone's interested:

s = input()

def max_occ(s):
s += ' '
count = 1
maxcount = 1
maxchar = s[0]
for i in range(1, len(s)):
if s[i-1] == s[i]:
count +=1
else:
if count > maxcount:
maxcount = count
maxchar = s[i-1]
count = 1
return {maxchar: maxcount}

print(max_occ(s))

[anishjain]

We can also do by taking num as key and char a value and update it

[josuegutierrezpalma]

why do we update prev_char=current? 4:23

[mikecheuk]

Can't believe I can code this on my own without looking into the solution! Thanks for providing the question!

[Kingstanding]

from collections import Counter as C
def f(string):
string = list(string)
most_common_value = C(string).most_common()[0]
return most_common_value

string = "AABCDDBBBEA"
f(string)

[justinschreiber]

move your second if to inside the first one to optimize further

[MichaelMantion]

So what if there is a tie??? Do you offer up the last tied string character or a previous one? because it sounds like you will only be giving the first longest set and ignoring all others.

[KumaranKM]

Python code without using hashmap:
s = input()
long = 0
count = 1
chat = s[0]
for i in range(1, len(s)):
if s[i-1] == s[i]:
count += 1
else:
if long < count:
long = count
chat = s[i-1]
count = 1
print(long, chat)

[terryrichards]

It would be faster if you moved the if count > max_count block inside the first else. You only need to check whether the substring is the longest found when you get to the end of it. You will also need to save prev_char as max_char instead of current.

[LondonAppDeveloper]

Loving the videos, thank you so much for creating and publishing them. How do you calculate the bit you mention at 0:48?

[bosteador]

I got this interview at Amazon. Completely threw me off and I failed it lol

[titouant]

It is better to return an object with two keys: one for the length of the longest run, and one for the letter that compose the longest run.

I wrote my solution in javascript:

function longestRun(s) {
let max = {letter:'', run:0};
let current = {letter:'', run:0};
for (let i = 0; i <= s.length; i++) {
if (current.letter !== s[i]) {
if (current.run > max.run) {
max.letter = current.letter;
max.run = current.run;
}
current.run = 0;
current.letter = s[i];
}
current.run++;
}
return max;
}

to test it on chrome or firefox: ctrl+maj+I then copy/paste in the console :)

[harshadshringi]

Nice job !! Even I got this as one of the interview question.

[mormubis]

I know it's been a long time from this video but also you assume the sequence doesn't have more than one longest consecutive character. (i.e.: 'AAABBB' solution: {'A': 3, 'B': 3}?)

[shreestuti]

What if the string is "AABCDDBBBEEEA". Both 'B' and 'E' have equal count. but according to the code above, it's taking only 'B'.

[siddhantdixit]

We can also create an array of each letter in the string and calculate the frequency and store it in array. The letter with max frequency will be the required letter.