4
\$\begingroup\$

I wrote code for the following problem:

Given a string, print out the number of deletions required so that the adjacent alphabets are distinct.

Please suggest different methods by which I can increase the speed of execution.

tst = int(input())
for i in range(0,tst):
    str = input()
    length = len(str)
    str = list(str)
    j=0;
    count = 0
    while(j<length):
       if(j+1<length):
            if((str[j] == str[j+1])):
                del str[j+1]
                count+=1
                length-=1
            else:
                j+=1
       else:
            j+=1
    print(count)
\$\endgroup\$
6
\$\begingroup\$

Here's your culprit:

del str[j+1]

When you remove one character from a string, all subsequent characters need to be shifted into the hole that you create. That changes your algorithm from O(Length) to a worst-case scenario of O(Length2), if every character is the same.

Additionally, your inner loop looks a lot like C code. Here is one way to reformulate it.

def count_consecutive_deletions(s):
    deletions = 0
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            deletions += 1
    return deletions

def testcases():
    for _ in range(int(input())):
        yield input()

for case in testcases():
    print(count_consecutive_deletions(case))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.