Finding the minimum number of required deletions to have a non-repeating string

Question

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)

Answer 1

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(Length²), 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))