[FIXED] Iterate a list to find a specific order of letters

Issue

I am working on this problem: https://dmoj.ca/problem/coci18c3p1

Basically, iterate a list of capital letters and find how many times the letters 'H', 'O', 'N' and 'I', in that exact order, there are.

Anything in between the first 'H' and the first 'O' gets ignored, even if it one of the target letters. Same for any letters in between the 'O' and the 'N'. And so on.

You just go from start to finish once. No combinations, permutations, etc.

Find the first 'H'. Then the first 'O', after the previous 'H'. Then the next 'N' after the previous 'O'. Etc.

They run a bunch of unit tests to make sure your code passes.

They do NOT tell you or show you the unit tests. Just the results.

My code cleanly passes the first six, but fails the last five.

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)

Solution

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)

Answered By - bgfvdu3w