How Can I Find The Longest Ascending Substring (or Tied Substrings)?

How to define a recurion-style function findmax which works like: findmax('abc')-->['abc'] findmax('afz')-->['afz'] findmax('cba')-->['c','b','a'] findmax('zfa')-->['z'

Solution 1:

If you really want a recursion-flavored function. I don't know if it's much more elegant, but I know it is less effective and much more limited than imperative style (recursion limit and tail calls) :

from collections import defaultdict

'''
    Return the "biggest" key (assuming keys are int).
    Should've used a ordered set instead of a dict
'''defmaxkey(dictio):
    returnmax ([ int(k) for k in dictio.keys() ])

'''
    Recursion-style of findmax. Notice the call to the same input string minus the first element,
    which indicate that the recursion isn't really much more efficient than imperative style.
    Also we have to take the maximum recursion limit into account (which should be attained in practice.)
'''deffindmax( input_string , tempbuffer = defaultdict(list), temp = ''):

    # End of the recursioniflen(input_string) == 0:
        tempbuffer[len(temp)].append(temp)          # add last element
        output = tempbuffer[maxkey(tempbuffer)]     # return the set of longest elements
        tempbuffer.clear()                          # pesky little mutable objects ...return output

    # Still elements in the input stringelse:
        first_char = input_string[0]

        # still ascending : bufferingiflen(temp) == 0or first_char > temp[-1]:
            temp   = temp + first_char
        # new string : store the old oneelse:
            tempbuffer[len(temp)].append(temp)
            temp   = first_char

        # Recursion call on the 'tail' of the input string, one character at a timereturn findmax( input_string[1:],tempbuffer, temp)




if __name__ == '__main__' :

    print findmax('abczabc')

    print findmax('abcabd')

Solution 2:

The following is a recursive solution. This function is purely recursive, no for loops or rather, no looping at all:

def find_max(s):
    _ret = []

    def string_iter(concat, compare):

        def appender():
            if len(concat) >= len(_ret[-1]):
                if len(concat) > len(_ret[-1]):
                    while _ret:
                        _ret.pop()
                _ret.append(concat)

        if len(compare) == 0:
            if len(_ret) != 0:
                appender()
            else:
                _ret.append(concat)
            return

        if concat[-1] < compare[0]:
            concat += compare[0]
            string_iter(concat, compare[1:])
        else:
            if len(_ret) != 0:
                appender()
            else:
                _ret.append(concat)
            string_iter(compare[0], compare[1:])

    string_iter(s[0], s[1:])

    return _ret

print find_max('abc')      # -->['abc']
print find_max('afz')      # -->['afz']
print find_max('cba')      # -->['c','b','a']
print find_max('zfa')      # -->['z','f','a']
print find_max('abczabc')  # --> ['abcz']
print find_max('abcabcpaidfbkjabdsfilabdfkabldfjadf')   # --> ['abcp', 'abdfk']

Solution 3:

There is no need for recursion at all.

def findmax(s):
    matches= []
    current= [s[0]]
    for index, characterin enumerate(s[1:]):
        if character>= s[index]:
            current.append(character)
        else:
            matches.append(current)
            current= [character]
    matches.append(current)
    maxlen = len(max(matches, key=len))
    return ["".join(match) formatchinmatches if len(match)==maxlen]

Test cases:

>>> findmax('abc')
['abc']
>>> findmax('afz')
['afz']
>>> findmax('cba')
['c', 'b', 'a']
>>> findmax('zfa')
['z', 'f', 'a']
>>> findmax('abczabc')
['abcz']
>>> findmax('abcabc')
['abc', 'abc']

Explanation can be found here (with a slightly modified version of this code).

Solution 4:

Adapting my solution to a previous answer:

import string

def findmax(s):
    groups = []
    cur_longest = ''
    prev_char = ''for c inmap(string.lower, s):
        if prev_char and c < prev_char:
            groups.append(cur_longest)
            cur_longest = c
        else:
            cur_longest += c
        prev_char = c
    groups.append(cur_longest)
    length = max([len(g) for g in groups])
    return [groupforgroupin groups iflen(group) == length]

Using it:

>>> findmax('abc') # expect: ['abc']['abc']
>>> findmax('afz') # expect: ['afz']['afz']
>>> findmax('cba') # expect: ['c','b','a']['c', 'b', 'a']
>>> findmax('zfa') # expect: ['z','f','a']['z', 'f', 'a']
>>> findmax('abczabc') # expect: ['abcz']['abcz']
>>> findmax('abcabc') # expect: ['abc','abc']['abc', 'abc']

Solution 5:

After studying the two answers from georgesl and Games Brainiac, I got a more satisfied solution combining both advantages of them.

Both of them are well designed in structure.

I think the advantage of georgesl's is : the design of tempbuffer dict object,while the one of Games Brainiac's is : the design of closure.

Although it is less effective , I am still very happy that there does exists a simple and elegant solution.

So, here I'd like to share :

from collections import defaultdict

deffindmax(s):
    buf=defaultdict(list)
    defrecur(s,mbr):
        if s=='':
            buf[len(mbr)].append(mbr)
            return buf[max(buf)]
        else:
            head=s[0]
            if mbr==''or mbr[-1]<head:
                mbr=mbr+head
            else:
                buf[len(mbr)].append(mbr)
                mbr=head
            return recur(s[1:],mbr)
    return recur(s,'')

if __name__ == '__main__' :
    print'abc',findmax('abc')
    print'afz',findmax('afz') 
    print'abcabcda',findmax('abcabcda')
    print'abczabcdabcd',findmax('abczabcdabcd')               
    print'zfa',findmax('zfa')
    print'zfa',findmax('zfa')

and here is the result:

>>> 
abc ['abc']
afz ['afz']
abcabcda ['abcd']
abczabcdabcd ['abcz', 'abcd', 'abcd']
zfa ['z', 'f', 'a']
zfa ['z', 'f', 'a']