Reputation: 181

Find the longest substring in alphabetical order

I have this code that I found on another topic, but it sorts the substring by contiguous characters and not by alphabetical order. How do I correct it for alphabetical order? It prints out lk, and I want to print ccl. Thanks

ps: I'm a beginner in python

s = 'cyqfjhcclkbxpbojgkar'
from itertools import count

def long_alphabet(input_string):
    maxsubstr = input_string[0:0] # empty slice (to accept subclasses of str)
    for start in range(len(input_string)): # O(n)
        for end in count(start + len(maxsubstr) + 1): # O(m)
            substr = input_string[start:end] # O(m)
            if len(set(substr)) != (end - start): # found duplicates or EOS
                break
            if (ord(max(sorted(substr))) - ord(min(sorted(substr))) + 1) == len(substr):
                maxsubstr = substr
    return maxsubstr

bla = (long_alphabet(s))
print "Longest substring in alphabetical order is: %s" %bla

Upvotes: 13

Answers (20)

tleo

Reputation: 361

s = 'cyqfjhcclkbxpbojgkar'
long_sub = '' #longest substring
temp = '' # temporarily hold current substr
if len(s) == 1: # if only one character
    long_sub = s
else:
    for i in range(len(s) - 1):
        index = i
        temp = s[index]
        while index < len(s) - 1: 
            if s[index] <= s[index + 1]:
                temp += s[index + 1]
            else:
                break
            index += 1
        if len(temp) > len(long_sub):
            long_sub = temp
        temp = ''
print(long_sub)

Upvotes: 0

kevin

Reputation: 1

```python
s = "cyqfjhcclkbxpbojgkar"  # change this to any word
word, temp = "", s[0]  # temp = s[0] for fence post problem
for i in range(1, len(s)):  # starting from 1 not zero because we already add first char
    x = temp[-1]  # last word in var temp
    y = s[i]  # index in for-loop
    if x <= y:
        temp += s[i]
    elif x > y:
        if len(temp) > len(word):  #storing longest substring so we can use temp for make another substring
            word = temp
        temp = s[i]  #reseting var temp with last char in loop
    if len(temp) > len(word):
        word = temp
print("Longest substring in alphabetical order is:", word)
```

My code store longest substring at the moment in variable temp, then compare every string index in for-loop with last char in temp (temp[-1]) if index higher or same with (temp[-1]) then add that char from index in temp. If index lower than (temp[-1]) checking variable word and temp which one have longest substring, after that reset variable temp so we can make another substring until last char in strings.

Upvotes: 0

KARAN KAJROLKAR

Reputation: 1

In some cases, input is in mixed characters like "Hello" or "HelloWorld"

**Condition 1:**order determination is case insensitive, i.e. the string "Ab" is considered to be in alphabetical order.

**Condition 2:**You can assume that the input will not have a string where the number of possible consecutive sub-strings in alphabetical order is 0. i.e. the input will not have a string like " zxec ".

   string ="HelloWorld"
    s=string.lower()
    r = ''
    c = ''
    last=''
    for char in s:
        if (c == ''):
            c = char
        elif (c[-1] <= char):
            c += char
        elif (c[-1] > char):
            if (len(r) < len(c)):
                r = c
                c = char
            else:
                c = char
    if (len(c) > len(r)):
        r = c
    for i in r:
        if i in string:
            last=last+i
        else:
            last=last+i.upper()
    if len(r)==1:
        print(0)
    else:
        print(last)

Out:elloW

Upvotes: 0

EakzIT

Reputation: 632

I had similar question on one of the tests on EDX online something. Spent 20 minutes brainstorming and couldn't find solution. But the answer got to me. And it is very simple. The thing that stopped me on other solutions - the cursor should not stop or have unique value so to say if we have the edx string s = 'azcbobobegghakl' it should output - 'beggh' not 'begh'(unique set) or 'kl'(as per the longest identical to alphabet string). Here is my answer and it works

n=0
for i in range(1,len(s)):
    if s[n:i]==''.join(sorted(s[n:i])):
        longest_try=s[n:i]
    else:
        n+=1

Upvotes: 0

yfpm2001

Reputation: 1

s=input()
temp=s[0]
output=s[0]
for i in range(len(s)-1):
    if s[i]<=s[i+1]:
        temp=temp+s[i+1]
        if len(temp)>len(output):
            output=temp           
    else:
        temp=s[i+1]

print('Longest substring in alphabetic order is:' + output)

Upvotes: 0

RamA

Reputation: 13

finding the longest substring in alphabetical order in Python

in python shell 'a' < 'b' or 'a' <= 'a' is True

result = ''
temp = ''
for char in s:
    if (not temp or temp[-1] <= char):
        temp += char
    elif (temp[-1] > char):
        if (len(result) < len(temp)):
            result = temp
        temp = char
    
if (len(temp) > len(result)):
    result = temp
    
print('Longest substring in alphabetical order is:', result)

Upvotes: 0

Buldo

Reputation: 99

Without using a library, but using a function ord() which returns ascii value for a character. Assumption: input will be in lowercase, and no special characters are used

s = 'azcbobobegghakl'

longest = ''

for i in range(len(s)):
    temp_longest=s[i]

    for j in range(i+1,len(s)):

        if ord(s[i])<=ord(s[j]):
            temp_longest+=s[j]
            i+=1
        else:
            break

    if len(temp_longest)>len(longest):
        longest = temp_longest

print(longest)

Upvotes: 1

m4110c

Reputation: 587

Wow, some really impressing code snippets here... I want to add my solution, as I think it's quite clean:

s = 'cyqfjhcclkbxpbojgkar'

res = ''
tmp = ''

for i in range(len(s)):
    tmp += s[i]
    if len(tmp) > len(res):
        res = tmp
    if i > len(s)-2:
        break
    if s[i] > s[i+1]:
        tmp = ''

print("Longest substring in alphabetical order is: {}".format(res))

Upvotes: 1

Pradosh

Reputation: 77

input_str = "cyqfjhcclkbxpbojgkar"
length = len(input_str) # length of the input string
iter = 0
result_str = '' # contains latest processed sub string
longest = '' # contains longest sub string alphabetic order 
while length > 1: # loop till all char processed from string
    count = 1
    key = input_str[iter] #set last checked char as key 
    result_str += key # start of the new sub string
    for i in range(iter+1, len(input_str)): # discard processed char to set new range
      length -= 1
      if(key <= input_str[i]): # check the char is in alphabetic order 
        key = input_str[i]
        result_str += key # concatenate the char to result_str
        count += 1
      else:
        if(len(longest) < len(result_str)): # check result and longest str length
          longest = result_str # if yes set longest to result
        result_str = '' # re initiate result_str for new sub string
        iter += count # update iter value to point the index of last processed char
        break

    if length is 1: # check for the last iteration of while loop
        if(len(longest) < len(result_str)):
          longest = result_str

print(longest);

Upvotes: 0

Sai

Reputation: 3

This worked for me

s = 'cyqfjhcclkbxpbojgkar'

lstring = s[0]
slen = 1

for i in range(len(s)):
    for j in range(i,len(s)-1):
            if s[j+1] >= s[j]:
                    if (j+1)-i+1 > slen:
                        lstring = s[i:(j+1)+1]
                        slen = (j+1)-i+1
            else:
                        break

print("Longest substring in alphabetical order is: " + lstring)

Output: Longest substring in alphabetical order is: ccl

Upvotes: 0

user3337142

Reputation: 41

s = 'cyqfjhcclkbxpbojgkar'
longest = ""
max =""

for i in range(len(s) -1):
    if(s[i] <= s[i+1] ):
       longest = longest + s[i]
       if(i==len(s) -2):
           longest = longest + s[i+1]
    else:
        longest  = longest + s[i]        
        if(len(longest) > len(max)):
            max = longest
        longest = ""        

if(len(s) == 1):
    longest = s


if(len(longest) > len(max)):
    print("Longest substring in alphabetical order is: " + longest)
else:
    print("Longest substring in alphabetical order is: " + max)

Upvotes: 3

prashasthbaliga

Reputation: 61

Use list and max function to reduce the code drastically.

actual_string = 'azcbobobegghakl'
strlist = []
i = 0
while i < len(actual_string)-1:
    substr = ''
    while actial_string[i + 1] > actual_string[i] :
        substr += actual_string[i]
        i += 1
        if i > len(actual_string)-2:
            break
    substr += actual-string[i]
    i += 1
    strlist.append(subst)
print(max(strlist, key=len))

Upvotes: 1

Rishith Poloju

Reputation: 169

s = "azcbobobegghakl"
ls = ""
for i in range(0, len(s)-1):
    b = ""
    ss = ""
    j = 2
    while j < len(s):
        ss = s[i:i+j]
        b = sorted(ss)
        str1 = ''.join(b)
        j += 1
        if str1 == ss:
            ks = ss
        else:
            break
    if len(ks) > len(ls):
        ls = ks
print("The Longest substring in alphabetical order is "+ls)

Upvotes: 0

Vladimir R

Reputation: 13

Another way:

s = input("Please enter a sentence: ")
count = 0
maxcount = 0
result = 0
for char in range(len(s)-1):
    if(s[char]<=s[char+1]):
       count += 1        
    if(count > maxcount):
           maxcount = count
           result = char + 1

    else:

        count = 0
startposition = result - maxcount
print("Longest substring in alphabetical order is: ", s[startposition:result+1])

Upvotes: -2

solution

Reputation: 199

s = 'cyqfjhcclkbxpbojgkar'
r = ''
c = ''
for char in s:
    if (c == ''):
        c = char
    elif (c[-1] <= char):
        c += char
    elif (c[-1] > char):
        if (len(r) < len(c)):
            r = c
            c = char
        else:
            c = char
if (len(c) > len(r)):
    r = c
print(r)

Upvotes: 19

J. A. Mendez

Reputation: 67

In a recursive way, you can import count from itertools

Or define a same method:

def loops( I=0, S=1 ):
    n = I
    while True:
        yield n
        n += S

With this method, you can obtain the value of an endpoint, when you create any substring in your anallitic process.

Now looks the anallize method (based on spacegame issue and Mr. Tim Petters suggestion)

def anallize(inStr):
    # empty slice (maxStr) to implement
    # str native methods
    # in the anallize search execution
    maxStr = inStr[0:0]
    # loop to read the input string (inStr)
    for i in range(len(inStr)):
        # loop to sort and compare each new substring
        # the loop uses the loops method of past
        # I = sum of: 
        #     (i) current read index
        #     (len(maxStr)) current answer length
        #     and 1
        for o in loops(i + len(maxStr) + 1):
            # create a new substring (newStr)
            # the substring is taked:
            # from: index of read loop (i)
            # to:   index of sort and compare loop (o)
            newStr = inStr[i:o]

            if len(newStr) != (o - i):# detect and found duplicates
                break
            if sorted(newStr) == list(newStr):# compares if sorted string is equal to listed string
                # if success, the substring of sort and compare is assigned as answer
                maxStr = newStr
    # return the string recovered as longest substring
    return maxStr

Finally, for test or execution pourposes:

# for execution pourposes of the exercise:
s = "azcbobobegghakl"
print "Longest substring in alphabetical order is: " + anallize( s )

The great piece of this job started by: spacegame and attended by Mr. Tim Petters, is in the use of the native str methods and the reusability of the code.

The answer is:

Longest substring in alphabetical order is: ccl

Upvotes: 2

Andrew Winterbotham

Reputation: 1010

Slightly different implementation, building up a list of all substrings in alphabetical order and returning the longest one:

def longest_substring(s):
    in_orders = ['' for i in range(len(s))]
    index = 0
    for i in range(len(s)):
        if (i == len(s) - 1 and s[i] >= s[i - 1]) or s[i] <= s[i + 1]:
            in_orders[index] += s[i]
        else:
            in_orders[index] += s[i]
            index += 1
    return max(in_orders, key=len)

Upvotes: 0

kirancodify

Reputation: 705

In Python character comparison is easy compared to java script where the ASCII values have to be compared. According to python

a>b gives a Boolean False and b>a gives a Boolean True

Using this the longest sub string in alphabetical order can be found by using the following algorithm :

def comp(a,b):
    if a<=b:
        return True
    else:
        return False
s = raw_input("Enter the required sting: ")
final = []
nIndex = 0
temp = []
for i in range(nIndex, len(s)-1):
    res = comp(s[i], s[i+1])
    if res == True:       
           if temp == []:
           #print i
               temp.append(s[i])
               temp.append(s[i+1])
           else:
               temp.append(s[i+1])
       final.append(temp)
        else:
       if temp == []:
        #print i
        temp.append(s[i])
       final.append(temp)
       temp = []
lengths = []
for el in final:
    lengths.append(len(el))
print lengths
print final
lngStr = ''.join(final[lengths.index(max(lengths))])
print "Longest substring in alphabetical order is: " + lngStr

Upvotes: 1

ejrb

Reputation: 338

You can improve your algorithm by noticing that the string can be broken into runs of ordered substrings of maximal length. Any ordered substring must be contained in one of these runs

This allows you to just iterate once through the string O(n)

def longest_substring(string):
    curr, subs = '', ''
    for char in string:
        if not curr or char >= curr[-1]:
            curr += char
        else:
            curr, subs = '', max(curr, subs, key=len)
    return max(curr, subs, key=len)

Upvotes: 4

Tim Peters

Reputation: 70735

Try changing this:

        if len(set(substr)) != (end - start): # found duplicates or EOS
            break
        if (ord(max(sorted(substr))) - ord(min(sorted(substr))) + 1) == len(substr):

to this:

        if len(substr) != (end - start): # found duplicates or EOS
            break
        if sorted(substr) == list(substr):

That will display ccl for your example input string. The code is simpler because you're trying to solve a simpler problem :-)

Upvotes: 5

Find the longest substring in alphabetical order

Answers (20)

finding the longest substring in alphabetical order in Python

Related Questions