CODEWITHSUNDEEP
pythonstringalgorithm
Sandy
Sandy

Reputation: 313

Find the longest substring with contiguous characters, where the string may be jumbled

Given a string, find the longest substring whose characters are contiguous (i.e. they are consecutive letters) but possibly jumbled (i.e. out of order). For example:
Input : "owadcbjkl"
Output: "adcb"
We consider adcb as contiguous as it forms abcd.

(This is an interview question.)

I have an idea of running a while loop with 2 conditions, one that checks for continuous characters using Python's ord and another condition to find the minimum and maximum and check if all the following characters fall in this range.

Is there any way this problem could be solved with low running time complexity? The best I can achieve is O(N^2) where N is the length of the input string and ord() seems to be a slow operation.

Upvotes: 0

Views: 2810

Answers (1)

jfs
jfs

Reputation: 414585

If the substring is defined as ''.join(sorted(substr)) in alphabet then:

  • there is no duplicates in the substring and therefore the size of the longest substring is less than (or equal to) the size of the alphabet

  • (ord(max(substr)) - ord(min(substr)) + 1) == len(substr), where ord() returns position in the alphabet (+/- constant) (builtin ord() can be used for lowercase ascii letters)

Here's O(n*m*m)-time, O(m)-space solution, where n is len(input_string) and m is len(alphabet):

from itertools import count

def longest_substr(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(substr)) - ord(min(substr)) + 1) == len(substr):
                maxsubstr = substr
    return maxsubstr

Example:

print(longest_substr("owadcbjkl"))
# -> adcb

Upvotes: 4

Related Questions