4
\$\begingroup\$

The code is meant to find the longest substring that is in alphabetical order.
I would like to know if I can do it more efficiently than I have done here. I am in my first week of my first introductory course, so I'm not looking for more advanced solutions. I just want to know if I'm not making it more complicated than necessary based on my current knowledge. I could't figure out how to use indexing for example.

s = 'azcbobobegghakl'

c = ""
d = ""
e = ""

for i in s:
    if c <= i:
        c = i
        d += c
        if len(d) > len(e):
            e = d
    else:
        c = i
        d = c
print('Longest substring in alphabetical order is: ' + e)
\$\endgroup\$
4
\$\begingroup\$

You are assigning c = i in both cases, which means you could pull this out and do this once unconditionally. This also will give you an idea of cs purpose and might give you ideas for how to name your variables in a better way. So trying to stay as close to your code as possible but with the suggested changes, your code could look something along the lines:

inputString = 'azcbobobegghakl'

prevChar = ""
currentString = ""
longestString = ""

for char in inputString:
    if prevChar <= char:
        currentString += char
        if len(currentString) > len(longestString):
            longestString = currentString
    else:
        currentString = char
    prevChar = char
print('Longest substring in alphabetical order is: ' + longestString )

Also I suggest you think about edgecases and treat these cases or at very least you make it clear (at least in a comment) what happens in those cases. As an idea of what I mean: what happens if there are several longest-strings of the same length? Which one should be printed? All? The first? The last? Just any one? What happens if the inputString is empty - your message will look a bit funny. You could output a different message in such a case.

You might think I‘m a bit pedantic, but I seriously recommend to think about your code in this way.

Other than that, I must admit I don‘t know python well enough to give you „the pythonic“ answer - I‘m not even sure if they use camelCase for python - still I hope you get the idea of the type of improvements I‘m recommending. Other than that your code looks ok to me.

\$\endgroup\$
  • 1
    \$\begingroup\$ Indeed, this is a recipe for any language but definitely that's not the convention for python variables \$\endgroup\$ – A. Romeu Feb 22 '18 at 0:29
1
\$\begingroup\$

Interesting one

I thought of using itertools, but seems that just enumerate and zip make the work

Added some docstrings, you can remove them for shorter code but helps explaining what happens in each list comprehension

If you neglect docstrings, code is a mere 5 lines :)

chars = 'azcbobobegghakl'

def smaller_than_previous(c, i):
    return c < chars[i-1] if i > 0 else False


def list_of_indexes_to_split(chars):
    """
    Returns a list of indexes where previous character is smaller than current

    eg for 'abcabcd': [0, 3]

    :param chars: string to check
    :return: list
    """
    return [0]+[i for i, c in enumerate(chars) if smaller_than_previous(c, i)]


def sliced_substrings(chars, indexes):
    """
    Returns a list of strings after slicing the original one using
    the indexes provided

    Eg for 'abcabcd', [0, 3]: ['abc', 'abcd']

    :param chars: string
    :param indexes: list with indexes where to slice
    :return: list of strings
    """
    return [chars[i:j] for i, j in zip(indexes, indexes[1:]+[None])]


indexes = list_of_indexes_to_split(chars)

parts = sliced_substrings(chars, indexes)

print(max(parts, key=len))
\$\endgroup\$
  • 1
    \$\begingroup\$ your smaller_than_previous does access global chars which is a design error. also it tries to handle i==0 which is better off in the comprehension. while I see the intention to name tricky expressions this is probably not the best example. as a whole this is definitely more pythonic but not necessarily more efficient. it could be if you maintained to work on indices till the very end. \$\endgroup\$ – stefan Feb 21 '18 at 21:37
  • \$\begingroup\$ chars can be passed as a parameter as well to that aux function, since is already a parameter in the first function Why this solution is also convenient is cause you generate a list with all substrings, which at some point you may want to use as well, as well as provides a solution to the problem of slicing strings based on index criteria, which groupby exercises rarely approach \$\endgroup\$ – A. Romeu Feb 22 '18 at 0:26
1
\$\begingroup\$

The other possible approach to this problem is to use numpy and it's array operations.

The proposed solution

import numpy

def find_longest_substring(input):
    start_indexes = []
    ascii_codes = numpy.array([ord(character) for character in input])
    ascii_codes = numpy.append(ascii_codes,0)

    ascii_diff = (numpy.diff(ascii_codes)>=0).astype(numpy.int)
    parts_ends = numpy.where(numpy.diff(ascii_diff)!=0)[0]+1
    parts_ends = numpy.diff(numpy.hstack((0, parts_ends)))
    max_substring_lenght = parts_ends.max()
    substring_starts = numpy.where(parts_ends==max_substring_lenght)[0]
    for start in list(substring_starts):
        start_indexes.append(sum(parts_ends[0:start]))
    return (max_substring_lenght+1, start_indexes)

(max_lenght, starts) = find_longest_substring('azcbobobegghakl')
print("Longest substring has {0} characters.".format(max_lenght))
for start in starts:
    print(start, max_lenght, s[start:start+max_lenght])

Step by step explanation

First lets take our input = 'azcbobobegghakl' and convert it into numpy array of ASCII codes (translation of characters into numbers, a...z characters are in order in ASCII table).

ascii_codes = numpy.array([ord(character) for character in input])

This Python style in-line loop iterates over all characters in string, and converts each one to it's ASCII representation using built-in ord() function. Now we would like to calculate difference between each neighboring elements of the array to check if next character is in alphabetical order (has same or grater ASCII value) or not (lower ASCII value). To be safe at the end of out input string lets add additional value 0 at the end of our array: ASCII codes for characters a...z are 97 to 122 so 0 will not affect the result. Since we want to append value at the end of array, using numpy.append() seems best choice:

ascii_codes = numpy.append(ascii_codes,0)

Now we use numpy.diff() to calculate differences between neighboring elements. If the difference between two characters is grater or equal 0, they are in ascending order. Since we want to keep only information if sequential characters are ascending we immediately compare calculated differences with 0. By default numpy returns boolean (True or False) values after comparison, so we need to force it to return integer (0 or 1) by adding .astype(numpy.int) - this will allow further operations:

ascii_diff = (numpy.diff(ascii_codes)>=0).astype(numpy.int)

At this point we have data vector with ones where characters are ascending and zeros elsewhere. All we need to do is find length and position of longest sequence of ones. By calculating numpy.diff() again we get non zero values where character sequence changes between ascending and descending. By using numpy.where() we obtain list of indexes where sequence change occurs (+1 is needed to allow finding ascending sequence at the beginning of string):

parts_ends = numpy.where(numpy.diff(ascii_diff)!=0)[0]+1

Now we have indexes of characters where sequence order changes, so to find sequences lengths we need to apply numpy.diff() again (this is the last time, I promise!). To correctly calculate length of first sequence we need to append 0 at the beginning of our list using numpy.hstack():

parts_ends = numpy.diff(numpy.hstack((0, parts_ends)))

Now we can find length of the longest ascending sequence:

max_substring_lenght = parts_ends.max()  

And get list of indexes where longest sequences start:

substring_starts = numpy.where(parts_ends==max_substring_lenght)[0]

Finally we need to loop over all indexes where longest sequences start, and calculate their position in input string by summing lengths of all sequences before itself. Indexes of longest sequences starts are appended to list introduced at the beginning of the function:

for start in list(substring_starts):
    start_indexes.append(sum(parts_ends[0:start]))

Result is returned as a tuple: length of longest sequence and list of positions of longest sequences in string. This result can be used to print all longest sequences:

(max_lenght, starts) = find_longest_substring('azcbobobegghakl')
print("Longest substring has {0} characters.".format(max_lenght))
for start in starts:
    print(start, max_lenght, s[start:start+max_lenght])

Performance

Using numpy and "Python approach" is usually faster than direct algorithm implementation, however in this case this doesn't seem obvious, due to solution complexity. To measure and compare performance results lets consider very long string:

s = 'azcbobobegghakl'*1000000 + 'zabcdefghija'*3 + 'azcbobobegghakl'*1000000

Searching for longest ordered substring should return three occurrences of 'abcdefghij'.

  • numpy based solution presented above outputted thee substrings in 6.853079 seconds
  • original solution by @Turluf outputted one substring in 8.956485 seconds
  • solution by @dingalapadum outputted one substring in 9.008759 seconds
  • solution by @A. Romeu outputted one substring in 9.946994 seconds
  • solution by @Maarten Fabré outputted thee substrings in 13.178466 seconds

The performance difference is not extraordinary, however clearly shows, that numpy solution wins.

\$\endgroup\$
1
\$\begingroup\$

naming

s, c, d and e are not clear variable names. Naming your variables well goes a long way to documenting your code

next char

The cleanest way to iterate over the next char is using zip and list indexing: for char, next_char in zip(s, s[1:]):

subsequent_chars = [s[0]]
longest_series = [s[0]]
for char, next_char in zip(s, s[1:]):
    if next_char >= char:
        subsequent_chars.append(next_char)
    else:
        substring = ''.join(subsequent_chars)
        if len(substring) > len(longest_series[0]):
            longest_series = [substring]
        elif len(substring) == len(longest_series[0]):
            longest_series.append(substring)
        subsequent_chars = [next_char]
longest_length = len(longest_series[0])
num_substrings = len(longest_series)
print(f'there are {num_substrings} with maximum length {longest_length}: {longest_series}')

the part of elif len(substring) == len(longest_series[0]): longest_series.append(substring) is only needed if you want to know all the substrings of that length

alternative versions

Inspired by @gozwei's answer, I came up with 2 different solutions. One only uses standard library, the other uses numpy. It does about the same as @gozwei's solution, but I think it is slightly clearer

For the first we will use itertools.accumulate to group the string in subsequent series of ascending characters. To do this, we need a helper generator, that yield False each time the string is not ascending.

We can use the pairwise itertools recipe, or zip and string indexing

def ascending_chars(s):
    yield False
    yield from (
        char >= next_char
        for char, next_char in pairwise(s)
        # for char, next_char in zip(s, s[1:])
    )

from itertool import tee, accumulate
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

The first yield False is to account for the first character in the string

import bisect
def find_subsequent_chars(original_string):
    rising = ascending_chars2(original_string)
    rising = accumulate(rising)
    rising = list(rising)
#     idx = max(groupby(rising), key=lambda x: iterlen(x[1]))[0]
    group = Counter(rising).most_common(1)[0][0]
    idx_min, idx_max = bisect.bisect_left(rising, group), bisect.bisect(rising, group)
    return original_string[idx_min, idx_max]

This algorithm does less than my original one. It just returns the first longest substring, unlike the other, which returns them all

numpy

def find_longest_substring_np(s):
    # s == 'azcbobobegghakl'
    arr = np.array(list(map(ord, s)), dtype='int16')
    diff = np.diff(arr) <= 0
    # diff == [False  True  True False  True False  True False False  True False True False False]
    group = np.append(np.zeros(1, dtype='int16'), diff.cumsum())
    # group == [0 0 1 2 2 3 3 4 4 4 5 5 6 6 6] 
    bins =  np.bincount(group)
    # bins == [2 1 2 2 3 2 3]
    max_count = np.max(bins)
    # max_count == 3
    groups = np.where(bins == max_count)[0]
    # groups = [4 6]
    for group_id in groups:
        indices = np.where(group == group_id)[0]
        # indices == [7 8 9] # group 4
        # indices == [12 13 14] # group 6
        idx_min = indices[0] # 7
        idx_max = indices[-1]+1 # 10
        yield s[idx_min: idx_max]

This one does more or less the same in numpy. The np.append is needed to take the first char in account. np.where returns a tuple, where the first element are the indices where the condition is True. bisect can also be used here to find idx_min and idx_max, and performance is about equal for the longer string.

This algorithm is about twice as fast as @gozwei's answer on my PC, and about 3 times as fast as the native implementation

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.