Iterate a list to find a specific order of letters-CodePudding

I am working on this problem:

I'm just looking to see if anybody can find a flaw in my logic and point it out to me.

I can't make it fail.

Samples:

input: HHHHOOOONNNNIIII output: 1

input: PROHODNIHODNIK output: 2

input: HONIIONIHHONI output: 2

input: HONIHONIHONI output: 3

input: HOHONINI output: 1

input: HIONHION output: 1

TLE means time limit exceeded. My code is to slow?

My code:

# DMOJ problem coci18c3p1
lst = list(input().upper())

if not 1 <= len(lst) <= 100000:
    print(0)
    raise SystemExit

filtered = [x for x in lst if x in 'HONI']
# print(filtered)

letters = 'H', 'O', 'N', 'I'

if any(i not in filtered for i in letters):
    print(0)
    raise SystemExit

count = 0

while True:
    if 'H' not in filtered:
        break
    h = filtered.index("H")
    count  = 1
    if h != 0:
        filtered = filtered[h:]

    if 'O' not in filtered:
        break
    o = filtered.index("O")
    count  = 1
    if o != 0:
        filtered = filtered[o:]

    if 'N' not in filtered:
        break
    n = filtered.index("N")
    count  = 1
    if n != 0:
        filtered = filtered[n:]

    if 'I' not in filtered:
        break
    i = filtered.index("I")
    count  = 1
    if i != 0:
        filtered = filtered[i:]

print(count//4)

CodePudding user response：

Yes, TLE means the tests are failing because your solution is not fast enough. Indeed, your solution makes many passes over the input. First, I'll go over the improvements you can make to your approach.

Instead of using a slice to create a new list, you can control the starting position of the search for index(). The second argument of that function is the index for the start of the search.

Instead of checking if the character is in the list, rely on catching the exception index() raises. This will avoid a redundant search (checking if the character exists requires a search).

The above may improve your time a bit, but it may not be good enough. It's actually possible to find the solution in a single pass. The basic idea is to keep track of which character you need to find next. For example, if you already found "H", then you need to look for "O". Once you have found "I", you can increment the count, and then start looking for "H" again.

# No need to convert the input into a list; a string can be indexed directly.
string = input().upper()
count = 0

targets = ["H", "O", "N", "I"]
target = 0

for i in range(len(string)):
    # Check if the current character matches the target.
    if string[i] == targets[target]:
        # There is a match. Move to the next target.
        # if the end is reached, cycle back to the first target (H).
        target = (target   1) % len(targets)

        # Check if the last target has been found.
        if string[i] == targets[-1]:
            count  = 1

print(count)