Minimize repetitions by removing all occurrences of one number

Question

I did a program in python3 which is correct, it gives the right results, but it has Time Complexity of O(n^2). I wanna improve the Time complexity of this program. When I run it on a platform algorea ,the program pass only 63% of tests (only 10 of 16 tests), because some tests take a long time. could you give me a better and efficient algorithm.

Problem Statement

In a list of integers, a repetition is a pair of equal numbers that are adjacent to each other. For example, in the list 1 3 3 4 2 2 1 1 1, there are four repetitions: the two 3's, then the two 2's, then the two 1's that follow, and finally the two 1's at the end of the list.

You are given a list of integers. Write a program that calculates the minimum number of repetitions that can remain in the list once all occurrences of one of the numbers are removed.

Output

You should output a single number: the minimum number of repetitions that can remain after removing all occurrences of one of the numbers in the list.

Examples

Here is an example of input:

liste = [1, 3, 2, 2, 3, 4, 4, 2, 1]

The list of 9 numbers is "1 3 2 2 3 4 4 2 1". It contains two repetitions (the first two 2's and the two 4's):

• Removing the 1's leaves the two repetitions;
• Removing the 2's brings the 3's together, so we removed one repetition and added one. There are still two repetitions left;
• Removing the 3's leaves the two repetitions;
• Removing the 4's leaves only one repetition.

If we remove all occurrences of the number 4, only one repetition remains. It is not possible to get fewer than this, so your program should output:

1

Constraints

• Time limit: 1000 ms.
• Memory limit: 64,000 kb.

The time limit is set so that a solution which iterates a small number of times over the entire list can score full points, but a solution which for each number in the list, loops over all other numbers in the list can only solve about half the tests without exceeding the time limit.

My Solution

liste = [1, 3, 2, 2, 3, 4, 4, 2, 1]
# liste = [1,3,3,4,2,2,1,1,1]

repmin=[]
listunique =set(liste)


for x in listunique:
  listWithoutx = []
  for i in liste:
    if i!=x:
      listWithoutx.append(i)
  rep=0
  for j in range(len(listWithoutx)-1):
    if listWithoutx[j]==listWithoutx[j+1]:
      rep+=1
  repmin.append(rep)

print(min(repmin))

How Could I improve the Time Complexity of this problem, like that the program run quickly.

Thanks in advance

Answer 1

Linear time (Attempt This Online!):

def min_repetitions(lst):
    total = 0
    remove = dict.fromkeys(lst, 0)
    a = b = None
    for c in lst:
        if c == b:
            total += 1
            remove[c] += 1
        else:
            if c == a:
                remove[b] -= 1
            a = b
            b = c
    return total - max(remove.values())

This keeps track of the last three values without reps as a, b and c, the total count of reps, and for each value, how many reps its removal would remove.

Btw putting it in a function makes variables faster and makes testing easier (you'll see some testing if you click the link).