Compute highest-scoring segmentation
I would suggest letting cost(i,j,k) be the cost of transforming [the first i-1 segments of clean, followed by the first j elements of the ith segment of clean] into [the first k elements of segmented].

You can then write a recurrence relation that expresses cost(i,j,k) in terms of values of cost(i,j-1,k), cost(i,j,k-1), and cost(i,j-1,k-1) (with a convention that cost(i,0,k) = cost(i-1,len(clean[i-1]),k)).  Then, you can use dynamic programming to fill in these values.