Python program to get the longest substring of the same character Given a word the program outputs the length of the longest substring with the same letters. For example:


long_repeat('sdsffffse') == 4
long_repeat('ddvvrwwwrggg') == 3
long_repeat('abababaab') == 2
long_repeat('') == 0


The code is:

def long_repeat(line):

    substrings = []
    current_substring = ""
    for i, letter in enumerate(line):
        if i == 0:
            current_substring = letter
        else:
            if letter == current_substring[len(current_substring) - 1]:
                current_substring += letter
                if(i == len(line)- 1):
                    substrings.append(current_substring)
            else:
                substrings.append(current_substring)
                current_substring = letter

    lengths = []
    for substring in substrings:
        lengths.append(len(substring))

    if len(lengths) &gt; 0:
        return  max(lengths)
    else:
        return 0


What could be improved?
I really like @Justin's answer, but I'm new here so I unfortunately cannot comment or upvote yet. So instead I'll take this opportunity to detail his answer in relation to your question.

The first thing to note, the methodologies of your (@enoy) solution and @Justin's is entirely different. Your solution is recreating the longest substring of the given string, then returning the length of the recreation. @Justin's solution is using simple math. To lay out the steps:


Create a beginning index, start at 0.
Traverse from the beginning index until the current letter and the previous letter are no longer the same. Record the index of the last letter that was repeating as an end index.
Subtract the two indexes
store the length in a variable, maybe called longest_length.
replace the beginning index with the end index + 1 (plus one because you want the rest of the input string and none of the previous substring)
repeat steps 2 and 3.
store the max of the longest_length and the length that was just found.
keep repeating 5 - 7 until the end of the input string
return longest_length


So with the steps lain out and clear, to answer your question:


  What could be improved?


If all you care about is the length of the longest substring, there shouldn't be a reason for you to recreate the substring in order to find its length. In terms of complexity, your space complexity is broken down like this:


substrings = [] - Since you're simply splitting the input string into substrings and storing them all into an array, this will always have a space complexity of \$n\$, where \$n\$ is the length of the input string.
current_substring = "" - If the entire input string is repeating, this can potentially be as large as \$n\$, where \$n\$ is the length of the input string.
lengths = [] - If the entire input string does not have a single repeating substring, this can potentially be as large as \$n\$, where \$n\$ is the length of the input string.


So all in all, you have a big O space complexity of \$O(3n)\$ or \$O(n)\$ (for something small like this I prefer not to simplify constants).

Where as @Justin's solution breaks down as so:


begin_index - Only stores a single value at any given time.
end_index - Only stores a single value at any given time.
longest_length - Only stores a single value at any given time.


So you can see how much smaller this is already, and in terms of big O space complexity, it's \$O(3)\$ or simplifies to \$O(1)\$.

All that was space complexity though, as for time complexity:

Let's start with your code breakdown again:


You traverse the input string once, to split each substring and record their lengths, so that time complexity is \$n\$, where \$n\$ is the length of the input string.
You then have to traverse your array lengths, and find the max using the max function, and if there's no repeating substring, that can potentially be \$n\$, where \$n\$ is the length of the input string.


So all in all, the time complexity is \$O(2n)\$

For @Justin's:


Traverse the list once, checking the max length of each substring as they're built so that's \$n\$, where \$n\$ is the length of the input string.


It's unavoidable, traversing the list at least once when doing anything involving comparisons, but you can see how work could have been combined into one loop, rather than two separate ones here.

And on closing notes, @Justin's solution can be easily adapted to store the substring simply with a variable named longest_substring = input_string[begin_index:end_index] if the longest_length variable changes. This is much smaller space than having an array of all substrings. 

Here is @Justin's answer I was talking about (which got deleted) -

# Function to return the ending index for the 
# largest valid subsring starting from index i
def end_of_uniform_substring(string, n, i): 
    i += 1
    while (i &lt; n):  
        current = string[i] 
        previous = string[i - 1] 
        #if the current character in the string 
        #is equal to the previous character
        if (current == previous):
            i += 1
        else: 
            break
    return i - 1

# Function to return the length of the  
# longest substring of consecutive 
# repeating letters in string   
def largest_substring(string, n): 
    length = 0
    i = 0
    while (i &lt; n): 
        # Valid substring exists from  
        # index i to end 
        end = end_of_uniform_substring(string, n, i) 
        # Update the length
        length = max(end - i + 1, length) 
        i = end + 1
    return length


Hope this helps!