Algorithm: Leetcode Contest 372

this contest has 3 problems which related to array-like structure, another 1 problem is bit manipulation, I will ignore this one.

2937. Make Three Strings Equal

You are given three strings s1, s2, and s3. You have to perform the following operation on these three strings as many times as you want.

In one operation you can choose one of these three strings such that its length is at least 2 and delete the rightmost character of it.

Return the minimum number of operations you need to perform to make the three strings equal if there is a way to make them equal, otherwise, return -1.

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {

        // find the longest prefix, then get the number of operations on each string
        int prefixLength = lengthOfCommonPrefix(s1, s2, s3);
        
        if(prefixLength < 1) {
            return -1;
        } else {
            return (s1.length() - prefixLength) + (s2.length() - prefixLength) + (s3.length() - prefixLength);
        }
    }
    
    private int lengthOfCommonPrefix(String s1, String s2, String s3) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] str3 = s3.toCharArray();
        
        int minLength = Math.min(str1.length, Math.min(str2.length, str3.length));
        
        int length = 0;
        while(length < minLength && str1[length] == str2[length] && str2[length] == str3[length]) {
            length++;
        }
        
        return length;
    }
}

2938. Separate Black and White Balls

There are n balls on a table, each ball has a color black or white.

You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.

In each step, you can choose two adjacent balls and swap them.

Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

Example 1:

Input: s = "101"
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "011".
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.

Solution 1

public long minimumSteps(String s) {
    long count = 0, res = 0;

    for(char c: s.toCharArray()) {
        if (c == '1') {
            count++;
        } else {
            res += count;
        }
    }

    return res;
}

solution 2

public long minimumSteps(String s) {
    long res = 0;

    char[] cArr = s.toCharArray();

    for(int i = 0, j = 0; i < cArr.length; i++) {
        if (cArr[i] == '0') {
            res += i - (j++);
        }
    }

    return res;
}

Retro

in this problem, I think the most difficulty part is the “minimum” part, actually I don’t know if the result is the minimum or not.

so when I first put hand on this problem, I use the bubble-sort way to solve, then the result is incorrect…

Then I look at the shared solution and inspired, essentially, this question is about, how many 1 are on the left of 0.

And finally I understand the meaning of “minimum”, it just remind us, just look at the essence of the problem, since it’s the most minimum result

2940. Find Building Where Alice and Bob Can Meet

You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.

If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].

You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.

Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

Example 1:

Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
Output: [2,5,-1,5,2]
Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2]. 
In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5]. 
In the third query, Alice cannot meet Bob since Alice cannot move to any other building.
In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].
In the fifth query, Alice and Bob are already in the same building.  
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Before Coding

my thoughts when I first time saw this problem, trying to solve the problem in following steps

1. given 2 indexes, find their common jumpable building
2. iterate the queries array to get the result

so in my opinion, the core problem of this problem is, how to find the common jumpable building of two given indexes

Solution

here is my solution

Retro

again I almost figure out the solution for this problem, the reason I didn’t get the solution is not 100% clear the case-by-case discussion.

I think the reason is when I did case-by-case discussion, I am not confident enough about the direction, so don’t understand each case very clearly and exit it very easily.

I denied some cases for the reason which doesn’t actually exist.

For example

• I am confused when the height of min index is higher than max index, how to iterate on the nextHigher index. I imagine there will be a zigzag thing like, find height[max] > height[min], then iterate on min index again…
• don’t fully understand mono-stack and the meaning of nextHigher array

So to be short, my abstraction ability is not good enough, so I cannot perform reasonable inference based on concrete examples.

The thinking ability of brain is not good enough as well…