### PROBLEM LINK:

**Author:** Shikhar Gupta

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

### PROBLEM:

There are **N** equal length carpet strips arranged adjacent to each other.

Every carpet strip is divided into **M** blocks which are either Clean (**‘C’**) or Dirty (**‘D’**).

We have to re-arrange the carpet strips in a way such that the area of clean portion gets maximized.

The problem can be solved using Dynamic Programming and a sorting.

### EXPLANATION:

We can visualize the floor as a matrix of blocks with each row representing a carpet strip.

Let the matrix be stored in **mp[][]** where **mp[i][j]** represents the **j**th block in the **i**th row.

Now we make a **dp[][]** in which **dp[j][i]** stores the number of consecutive clean blocks to the left of the **j**th block in the **i**th row.

Now we sort each of the rows in the **dp** matrix (The sorting can be done in ***O(N)***) and iterate through each of the rows to find the maximum value of **dp[i][j]*(n-j+1)**.

### AUTHOR’S SOLUTIONS:

Author’s solution can be found here.