1578. Minimum Time to Make Rope Colorful

First though...linear scan and using min heap

T: O(n*nlogn)

```java
class Solution {
    public int minCost(String colors, int[] neededTime) {
        char pre = colors.charAt(0);
        int i = 1;
        int result = 0;
        Queue<Integer> minHeap = new PriorityQueue<>();
        while (i < colors.length()) {
            if (colors.charAt(i) == pre) {
                minHeap.offer(neededTime[i-1]);
                while (i < colors.length() && colors.charAt(i) == pre) {
                    minHeap.add(neededTime[i]);
                    i++;
                }
                while (!minHeap.isEmpty() && minHeap.size() > 1) {
                    System.put.println(minHeap.get())
                    result += minHeap.poll();
                }
                pre = colors.charAt(i-1);
            } else {
                i++;
                pre = colors.charAt(i-1);
            }
        }
        return result;
    }
}

/***
if same -> remove and add these all same to pq
if not same -> step2: pop pq until one (min heap), add these pop time to result
end aslo step2
 */
```

actually can use 2 pointers

utilize every group's max and total

we can find ans is = total - max

```java
class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();
        int left = 0;
        int right = 0;
        int result = 0;
        while (left < n && right < n) {
            int total = 0;
            int curMax = 0;
            while (right < n && colors.charAt(left) == colors.charAt(right)) {
                total += neededTime[right];
                curMax = Math.max(curMax, neededTime[right]);
                right++;
            }
            result += total - curMax;
            left = right;
            if (left < n && right < n && colors.charAt(left) != colors.charAt(right)) {
                left++;
                right++;
            }
        }
        return result;
    }
}

/***
T: O(n)
S: O(1)

2 pointers
idea: same color group, we get the max and total
ans is the 
sum of each group's (group total - group max)

 */
```

more fast, we can only one pass

we only add smaller number to result, how to do it?

maintain a max value for each round, then we can only can smaller one to result (when change group, just reset it's to new group init max)

```java
class Solution {
    public int minCost(String colors, int[] neededTime) {
        int n = colors.length();
        int result = 0;
        int curMax = neededTime[0];
        char[] colorChar = colors.toCharArray();
        for (int i = 1; i < n; i++) {
            if (colorChar[i] != colorChar[i-1]) { // compare to pre
                curMax = neededTime[i]; // when different group color, reset curMax to cur
            } else {
                result += Math.min(neededTime[i], curMax); // add smaller one every time
                curMax = Math.max(neededTime[i], curMax);
            }
        }
        return result;
    }
}

/***
T: O(n)
S: O(1)


 */
```